Easy to understand Segment Tree Code!
IntuitionIf you know about Segment Tree then the question is not hard at all. The challenge is to create the range with the commpresed indexes for the sqaures.A
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
If you know about Segment Tree then the question is not hard at all. The challenge is to create the range with the commpresed indexes for the sqaures.

# Approach
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity:
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```cpp []
class SegTree{
    vector<int>seg;
    public:
    SegTree(int n){
        seg.resize(4*n+1, 0);
    }
    int query(int ind, int low, int high, int l, int h){
        if(h<low || high<l) return 0;
        if(low>=l && high<=h) return seg[ind];

        int mid = (low + high)/2;
        int left = query(2*ind+1, low, mid, l, h);
        int right = query(2*ind+2, mid+1, high, l, h);
        return max(left, right);
    }

    void update(int ind, int low, int high, int l, int h,int val){
        if(h<low || l>high) return;
        if(low == high){
            seg[ind] = max(seg[ind], val);
            return;
        }
        int mid = (low + high) /2;
        update(2*ind+1, low, mid, l, h, val);
        update(2*ind+2, mid+1, high, l, h, val);
        seg[ind] = max(seg[2*ind+1], seg[2*ind+2]);
    }
};

class Solution {
public:
    vector<int> fallingSquares(vector<vector<int>>& positions) {
        set<int>sortedCords;
        map<int, int>mpp;
        for(auto pos : positions){
            sortedCords.insert(pos[0]);
            sortedCords.insert(pos[0]+pos[1]-1);
        }
        int count = 1;
        for(int cords : sortedCords){
            mpp[cords] = count++;
        }
        int n = count;
        SegTree ob(n);
        vector<int>ans;
        int maxi = 0;

        for(auto& pos : positions){
            int l = mpp[pos[0]];
            int r = mpp[pos[0]+pos[1]-1];
            int maxHeight = ob.query(0, 1, n, l, r);
            ob.update(0, 1, n, l, r, maxHeight+pos[1]);

            maxi = max(maxi , ob.query(0, 1, n, 1, n));
            ans.push_back(maxi);
        }
        return ans;
    }
};

```
['Segment Tree', 'Ordered Set', 'C++']