C++ BST Solution detailed with comments
Approach\nWe can store closed-open intervals $[i,~j)$ in a BST such that\n\n a < b $\Leftrightarrow$ the whole a interval is to the left of b\n a > b $\Leftrigh
# Approach\nWe can store closed-open intervals $[i,~j)$ in a BST such that\n\n* `a < b` $\\Leftrightarrow$ the whole `a` interval is to the left of `b`\n* `a > b` $\\Leftrightarrow$ the whole `a` interval is to the right of `b`\n* `a == b` $\\Leftrightarrow$ `a` intercepts `b`\n\nDetails on how to do that are in the code and [my solution for 729. My Calendar I](https://leetcode.com/problems/my-calendar-i/solutions/5438715/just-use-a-set).\n\nBy addind a height to these intervals, we have rectangles.\n\nSo, for each step, we can take the lower bound and the upper bound of the new square to be added to find which rectangles intercepts with it. Then, we replace those with 3 rectangles:\n\n* the first one being the little tip that comes from the first intercepting rectangle\n* the second being a rectangle that have the width of the new square and the height of the heighest intercepting rectangle\n* The third being the little tip that comes from the last intercepting rectangle\n\nThe images represent this mechanism with some possible scenarios\n\n![image.png](https://assets.leetcode.com/users/images/071be687-5ba0-44ac-9026-0ca29a005eea_1723034251.3841434.png)\n\n![image.png](https://assets.leetcode.com/users/images/5d7a3b9c-4a67-43a6-b80f-e719cdc6d5f2_1723033335.8963501.png)\n\n![image.png](https://assets.leetcode.com/users/images/5d53223f-b62b-4c70-9c4d-8e09472476db_1723033489.3163388.png)\n\n\n# Complexity\n- Time complexity:\n$$O(n \\cdot \\log(n))$$ - we can find all intercepting rectangles in $O(\\log(n))$ time and we do this $n$ times.\nThe inner iteration is amortized $O(n)$, so we get $O(n\\cdot\\log(n))$ as our complexity.\n\n- Space complexity:\n$$O(n)$$ for the result array and $$O(n)$$ for the BST (worst case).\n\n# Code\n```\nclass Solution {\nprivate:\n  struct Rect {\n    int begin;\n    int end;\n    int height;\n  };\n\n  struct Compare {\n    // this comparator is quite something...\n    // with this, equality happens when an interval intersects another\n    // considering an interval as [a, b)\n    bool operator()(const Rect& a, const Rect& b) const {\n      // scenarios:\n      // a < b (the whole interval a is to the left of b):\n      // [   )         |  [   )\n      //     [      )  |           [   )\n      // a > b (the whole interval a is to the right of b):\n      //    [    )     |         [  )\n      // [  )          | [   )\n      // a == b (a intersects b):\n      // [    )        |    [    ) \n      //    [    )     | [    )\n      return a.end <= b.begin;\n    }\n  };\n\n  typedef set<Rect, Compare> RectTree;\npublic:\n  vector<int> fallingSquares(vector<vector<int>>& positions) {\n    // with this bad boy, lookup is done in O(log(n)) time\n    RectTree rects;\n\n    vector<int> result;\n    // this makes our .push_back\'s efficient\n    result.reserve(positions.size());\n\n    int max_height = 0;\n\n    for (const auto& p: positions) {\n      const int begin = p[0];\n      const int end = p[0] + p[1];\n      const int height = p[1];\n\n      // this is the first rect in the tree that intercepts with our new rectangle\n      const auto lb = rects.lower_bound({ begin, end, height });\n      // and this is the first rect after ours that DOESN\'t intercept with it\n      const auto ub = rects.upper_bound({ begin, end, height });\n\n      int max_height_in_interval = 0;\n\n      // so, we\'re gonna iterate over these elements, find the greatest height of them\n      // and delete them\n      for (auto it = lb; it != ub; ) {\n        // since we\'re erasing the iterator from the tree, we must grab its information\n        // (we\'ll need it later on this iteration)\n        const auto [b, e, h] = *it;\n\n        max_height_in_interval = max(max_height_in_interval, h);\n\n        // we must grab the next iterator right away since we\'re modifying the tree\n        // while iterating\n        auto nxt = next(it);\n        rects.erase(it);\n        it = nxt;\n\n        // if we find a rect that starts before our current rect begins\n        // we must re-insert the little tip of the previous square\n        if (b < begin) {\n          rects.insert({ b, begin, h });\n        }\n        \n        // same for a rect that ends after our current rect ends\n        if (e > end) {\n          rects.insert({ end, e, h });\n        }\n      }\n\n      const int new_height = max_height_in_interval + height;\n\n      // after deleting all intercepting rects, we have room for our new big rect\n      rects.insert({ begin, end, new_height });\n\n      // finally, we can update the result array\n      result.push_back(max_height = max(max_height, new_height));\n    }\n\n    return result;\n  }\n};\n\n```
['Binary Search Tree', 'Ordered Set', 'C++']