Iterative Segment Tree
Segment Tree\nI used the iterative implemnetation of segment tree instead of recursive and coordinate compression by binary search\n\n# Complexity\n- Time compl
# Segment Tree\nI used the iterative implemnetation of segment tree instead of recursive and coordinate compression by binary search\n\n# Complexity\n- Time complexity:\nO(n^2) as instead of performing Lazy Propagation, we can increase the elements falling in range of square edge one by one.\n\n# Code\n```\ntypedef long long ll;\nll N = (ll)1e5;\nll tree[(ll)2e5];\n\nvoid build(ll n)\n{\n    for(int i=n-1; i>0; i--)\n    {\n        tree[i] = max(tree[i<<1], tree[i<<1|1]);\n    }\n}\n\nvoid modify(ll p, ll val, ll n)\n{\n    for(tree[p+=n] = val; p>1; p>>=1)\n    {\n        tree[p>>1] = max(tree[p], tree[p^1]);\n    }\n}\n\nll query(ll l, ll r, ll n)\n{\n    ll res = 0;\n    for(l+=n, r+=n; l<r; l>>=1, r>>=1)\n    {\n        if(l&1) res = max(res, tree[l++]);\n        if(r&1) res = max(res, tree[--r]);\n    }\n    return res;\n}\n\nclass Solution {\npublic:\n    vector<int> fallingSquares(vector<vector<int>>& positions) {\n        memset(tree,0,sizeof(tree));\n        set<ll> id;\n        vector<ll> idx;\n        unordered_map<ll,ll> mp;\n        for(ll i=0; i<positions.size(); i++)\n        {\n            id.insert(positions[i][0]);\n            id.insert(positions[i][0]+positions[i][1]);\n        }\n        for(auto x:id) idx.push_back(x);\n        ll n = idx.size();\n        sort(idx.begin(), idx.end());\n        vector<int> ans;\n        for(ll i=0; i<positions.size(); i++)\n        {\n            ll l = lower_bound(idx.begin(), idx.end(), positions[i][0]) - idx.begin();\n            ll r = lower_bound(idx.begin(), idx.end(), positions[i][0]+positions[i][1]) - idx.begin()-1;\n            ll mx = query(l,r+1,n);\n            for(ll j=l; j<=r; j++)\n            {\n                modify(j,mx+positions[i][1],n);\n            }\n            ans.push_back(query(0,n-1,n));\n        }\n        return ans;\n    }\n};\n```
['Segment Tree', 'C++']