c++ | easy | short
\n# Code\n\nclass Solution {\npublic:\n    unordered_map<int, int> mp; //used for compression\n    int tree[8000]; //tree[i] holds the maximum height for its co
\n# Code\n```\nclass Solution {\npublic:\n    unordered_map<int, int> mp; //used for compression\n    int tree[8000]; //tree[i] holds the maximum height for its corresponding range\n    \n    void update(int t, int low, int high, int i, int j, int h){\n        if(i>j)\n            return;\n        if(low==high){\n            tree[t]=h;\n            return;\n        }\n        int mid=low+((high-low)/2);\n        update(2*t, low, mid, i, min(mid, j), h);\n        update(2*t+1, mid+1, high, max(mid+1, i), j, h);\n        tree[t]=max(tree[2*t], tree[2*t+1]);\n    }\n    \n    int query(int t, int low, int high, int i, int j){\n        if(i>j)\n            return -2e9;\n        if(low==i && high==j)\n            return tree[t];\n        int mid=low+((high-low)/2);\n        return max(query(2*t, low, mid, i, min(mid, j)), query(2*t+1, mid+1, high, max(mid+1, i), j));\n    }\n    \n    vector<int> fallingSquares(vector<vector<int>>& positions) {\n        set<int> s;\n        memset(tree, 0, sizeof(tree));\n        for(auto it: positions){\n            s.insert(it[0]);\n            s.insert(it[0]+it[1]-1);\n        }\n        int compressed=1, n=positions.size();\n        vector<int> ans(n);\n        for(auto it: s)\n            mp[it]=compressed++;\n        for(int i=0; i<n; i++){\n            int start=positions[i][0], end=positions[i][1]+start-1, h=positions[i][1];\n            int curr=query(1, 1, 2*n, mp[start], mp[end]), ncurr=curr+h;\n            update(1, 1, 2*n, mp[start], mp[end], ncurr);\n            ans[i]=tree[1]; \n        }\n        return ans;\n    }\n};\n```
['C++']