Segment Tree Lazy Propagation || O(nlog(n)) || C++
I used an unordered map as the container of the segment tree, whose expected complexity is O(1).\n\n\nvector<int> fallingSquares(vector<vector<int>>& p) {\n    
I used an unordered map as the container of the segment tree, whose expected complexity is O(1).\n\n```\nvector<int> fallingSquares(vector<vector<int>>& p) {\n    segment_tree seg((int)(1e8+1e6)+1);   //Boundary position\n    int mx = 0;\n    vector<int> ans;\n    for(int i = 0; i < p.size(); i++) {\n        int h = p[i][1] + seg.query(p[i][0]+1, p[i][0] + p[i][1]);\n        seg.update(p[i][0]+1, p[i][0]+p[i][1], h);\n        mx = max(mx, h);\n        ans.push_back(mx);\n    }\n    return ans;\n}\n```\nSegement Tree implementation:\n```\nclass segment_tree {\nunordered_map<unsigned int, int> seg;\nunordered_map<unsigned int, int> lazy;\n\nint size;\nbool invalid(int x, int y) {\n    return x > y;\n}\nbool out_range(int a, int b, int x, int y) {\n    return a > y || b < x;\n}\nbool in_range(int a, int b, int x, int y) {\n    return a <= x && y <= b;\n}\nvoid propagate(int k, int x, int y, int val) {\n    seg[k] = val;\n    if(x != y)\n        lazy[2*k] = val, lazy[2*k+1] = val;\n}\nvoid lazy_update(int k, int x, int y) {\n    if(lazy[k]) {\n        seg[k] = lazy[k];\n        if(x != y)\n            lazy[2*k] = lazy[k], lazy[2*k+1] = lazy[k];\n        lazy[k] = 0;\n    }\n}\npublic:\nsegment_tree(int n) {\n    size = n+1;\n}\nvoid update(int l, int r, int val) {\n    update(l, r, 1, 0, size-1, val);\n}\nvoid update(int a, int b, int k, int x, int y, int val) {\n    if(invalid(x, y)) return;\n    lazy_update(k, x, y);\n    if(out_range(a, b, x, y)) return;\n    if(in_range(a, b, x, y)) {propagate(k, x, y, val); return;}\n    int d = (x+y) / 2;\n    update(a, b, 2*k, x, d, val);\n    update(a, b, 2*k+1, d+1, y, val);\n    seg[k] = max(seg[2*k], seg[2*k+1]);\n}\nint query(int l, int r) {\n    return query(l, r, 1, 0, size-1);\n}\nint query(int a, int b, int k, int x, int y) {\n    if(invalid(x, y)) return INT_MIN;\n    lazy_update(k, x, y);\n    if(out_range(a, b, x, y)) return INT_MIN;\n    if(in_range(a, b, x, y)) return seg[k];\n    int d = (x+y)/2;\n    return max(\n    query(a, b, 2*k, x, d), \n    query(a, b, 2*k+1, d+1, y)\n    );\n}\n};\n```
['Tree', 'C']