C++  segment tree
\nclass node\n{\n  public:\n    int hei,max_hei;\n    int s,e;\n    node* l;\n    node* r;\n    node(int s,int e):hei(0),max_hei(0),s(s),e(e),l(NULL),r(NULL)\n 
```\nclass node\n{\n  public:\n    int hei,max_hei;\n    int s,e;\n    node* l;\n    node* r;\n    node(int s,int e):hei(0),max_hei(0),s(s),e(e),l(NULL),r(NULL)\n    {}\n};\nclass Solution {\n    \n    public:\n    node* build(vector<int>&nums,int s,int e)\n    {\n        if(s>=e)\n            return NULL;\n        if(e-s==1)\n            return new node(nums[s],nums[e]);\n        \n        int mid=(s+e)/2;\n        \n        node* root=new node(nums[s],nums[e]);\n        \n        root->l=build(nums,s,mid);\n        root->r=build(nums,mid,e);\n        \n        return root;\n    }\n    \n    int find(node* root,int s,int e)\n    {\n        if(e<=root->s || s>=root->e)\n            return INT_MIN;\n        \n        if(s<=root->s && e>=root->e)\n        {\n            return root->max_hei;\n        }\n        else\n        {\n            int l=find(root->l,s,e);\n            int r=find(root->r,s,e);\n            \n            return max(root->hei,max(l,r));\n        }\n    }\n    void update(node* root,int s,int e,int val)\n    {\n        \n        if(e<=root->s || s>=root->e)\n            return;\n                \n        if(s<=root->s && e>=root->e)\n        {\n            root->hei=val;\n            root->max_hei=max(root->max_hei,root->hei);\n        }\n        else\n        {\n            update(root->l,s,e,val);\n            update(root->r,s,e,val);\n            root->max_hei=max(root->hei,max(root->l->max_hei,root->r->max_hei));\n        }\n    }\n    \n   vector<int> fallingSquares(vector<vector<int>>& rect){\n        set<int>st;\n       \n        for(vector<int> &v:rect)\n        {    \n            st.insert(v[0]);  \n            st.insert(v[1]+v[0]);\n        } \n        vector<int>x;\n        for(auto &i:st)\n            x.push_back(i);\n        \n        node* root=build(x,0,x.size()-1);\n        vector<int>ans;\n        for(auto & v:rect)\n        {\n            int val=0;\n            int res=find(root,v[0],v[0]+v[1]);\n            update(root,v[0],v[0]+v[1],res+v[1]);\n           \n            ans.push_back(root->max_hei);\n        } \n        return ans;\n    }\n};\n```
[]