C++ Segment Tree with range compression (easy & compact)
It is a good practice to use lazy propagation with range updates but since this problem has lesser number of points (1000), we can normally do it with segment t
It is a good practice to use lazy propagation with range updates but since this problem has lesser number of points (1000), we can normally do it with segment tree and range compression (otherwise both memory and time exceeds). \n\nIf you are not good at segment trees please read the following artice: https://cp-algorithms.com/data_structures/segment_tree.html\n\n```\nclass Solution {\npublic:\n    \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]; //maximum height across all points till now\n        }\n        return ans;\n    }\n};\n```
[]