Segment tree with lazy propagation and coordinates compression
Understand the problem first\nInput: positions = [[1, 2], [2, 3], [6, 1]]\nAnd it will look like below, so you can easily get the result: [2, 5, 5]\n\n\nWith th
## Understand the problem first\nInput: `positions = [[1, 2], [2, 3], [6, 1]]`\nAnd it will look like below, so you can easily get the result: `[2, 5, 5]`\n![image](https://assets.leetcode.com/users/images/01eff168-05ee-415d-9948-9d687339db9e_1615006427.5494444.png)\n\nWith that, we can come up with the straightforward `O(N^2)` solution:\n```java\npublic List<Integer> fallingSquares(int[][] positions) {\n      int[] heights = new int[positions.length];\n\n      List<Integer> ans = new ArrayList<>();\n      int cur = 0;\n      for (int i = 0; i < heights.length; ++i) {\n          int left = positions[i][0];\n          int size = positions[i][1];\n          int right = left + size - 1;\n          heights[i] += size;\n\n          for (int j = i + 1; j < heights.length; ++j) {\n              int left2 = positions[j][0];\n              int size2 = positions[j][1];\n              int right2 = left2 + size2 - 1;\n              if (left2 <= right && right2 >= left) {\n                  heights[j] = Math.max(heights[i], heights[j]);\n              }\n          }\n          cur = Math.max(cur, heights[i]);\n          ans.add(cur);\n      }\n      return ans;\n  }\n```\n\n## Segment tree with lazy propagation using array\nAn example of Segment tree:\n![image](https://assets.leetcode.com/users/images/4b6023df-111e-4952-9222-0f5bfc9d41d9_1615006746.9659917.png)\n\n```java\nclass SegmentTree {\n\tprivate int[] tree;\n\tprivate int[] lazy;\n\tprivate int n;\n\n\tpublic SegmentTree(int n) {\n\t\tthis.n = n;\n\t\tint len = (1 << (1 + (int)(Math.ceil(Math.log(n) / Math.log(2))))) - 1;\n\t\ttree = new int[len];\n\t\tlazy = new int[len];\n\t}\n\n\tpublic int query(int left, int right) {\n\t\treturn queryCore(left, right, 0, n - 1, 0);\n\t}\n\n\tpublic void update(int left, int right, int newVal) {\n\t\tupdateCore(left, right, 0, n - 1, 0, newVal);\n\t}\n\n\tprivate int queryCore(int left, int right, int segLeft, int segRight, int index) {\n\t\tif (lazy[index] != 0) {\n\t\t\t// Execute un-merged update.\n\t\t\texecute(index, lazy[index], segLeft, segRight);\n\t\t\t// Clear merged update.\n\t\t\tlazy[index] = 0;\n\t\t}\n\n\t\tif (left > segRight || right < segLeft) {\n\t\t\treturn 0;\n\t\t}\n\n\t\tif (left <= segLeft && segRight <= right) {\n\t\t\treturn tree[index];\n\t\t}\n\n\t\tint mid = getMid(segLeft, segRight);\n\t\treturn merge(queryCore(left, right, segLeft, mid, index * 2 + 1),\n\t\t\tqueryCore(left, right, mid + 1, segRight, index * 2 + 2));\n\t}\n\n\tprivate void updateCore(int left, int right,\n\t\t\t\t\t\t\tint segLeft, int segRight, int index, int newVal) {\n\t\tif (lazy[index] != 0) {\n\t\t\texecute(index, lazy[index], segLeft, segRight);\n\t\t\tlazy[index] = 0;\n\t\t}\n\n\t\tif (left > segRight || right < segLeft) {\n\t\t\treturn;\n\t\t}\n\n\t\tif (left <= segLeft && segRight <= right) {\n\t\t\t// Execute update for newVal.\n\t\t\texecute(index, newVal, segLeft, segRight);\n\t\t\treturn;\n\t\t}\n\n\t\tint mid = getMid(segLeft, segRight);\n\t\tupdateCore(left, right, segLeft, mid, index * 2 + 1, newVal);\n\t\tupdateCore(left, right, mid + 1, segRight, index * 2 + 2, newVal);\n\n\t\ttree[index] = merge(tree[index * 2 + 1], tree[index * 2 + 2]);\n\n\t}\n\n\tprivate void execute(int index, int update, int segLeft, int segRight) {\n\t\t// Apply the udpate.\n\t\ttree[index] = merge(tree[index], update);\n\t\tif (segLeft != segRight) {\n\t\t\t// Propagate the update to children.\n\t\t\tlazy[2 * index + 1] = merge(lazy[2 * index + 1], update);\n\t\t\tlazy[2 * index + 2] = merge(lazy[2 * index + 2], update);\n\t\t}\n\t}\n\n\tprivate int merge(int x, int y) {\n\t\treturn Math.max(x, y);\n\t}\n\n\tprivate int getMid(int left, int right) {\n\t\treturn left + (right - left) / 2;\n\t}\n}\n```\n\n## Segment tree with lazy propagation using binary tree\n```java\nclass SegmentTree {\n\tprivate Node root;\n\n\tpublic SegmentTree(int n) {\n\t\tthis.root = new Node(0, 0, n - 1);\n\t}\n\n\tpublic int query(int left, int right) {\n\t\treturn queryCore(left, right, root);\n\t}\n\n\tpublic void update(int left, int right, int newVal) {\n\t\tupdateCore(left, right, root, newVal);\n\t}\n\n\tprivate int queryCore(int left, int right, Node cur) {\n\t\tif (cur == null) {\n\t\t\treturn 0;\n\t\t}\n\n\t\tif (cur.lazyVal != 0) {\n\t\t\t// Execute un-merged update.\n\t\t\texecute(cur, cur.lazyVal);\n\t\t\t// Clear merged update.\n\t\t\tcur.lazyVal = 0;\n\t\t}\n\n\t\tif (left > cur.high || right < cur.low) {\n\t\t\treturn 0;\n\t\t}\n\n\t\tif (left <= cur.low && cur.high <= right) {\n\t\t\treturn cur.val;\n\t\t}\n\n\t\treturn merge(queryCore(left, right, cur.left),\n\t\t\tqueryCore(left, right, cur.right));\n\t}\n\n\tprivate void updateCore(int left, int right, Node cur, int newVal) {\n\t\tif (cur.lazyVal != 0) {\n\t\t\t// Execute un-merged update.\n\t\t\texecute(cur, cur.lazyVal);\n\t\t\t// Clear merged update.\n\t\t\tcur.lazyVal = 0;\n\t\t}\n\n\t\tif (left > cur.high || right < cur.low) {\n\t\t\treturn;\n\t\t}\n\n\t\tif (left <= cur.low && cur.high <= right) {\n\t\t\t// Execute update for newVal.\n\t\t\texecute(cur, newVal);\n\t\t\treturn;\n\t\t}\n\n\t\tint mid = getMid(cur.low, cur.high);\n\t\tif (cur.left == null) {\n\t\t\tcur.left = new Node(0, cur.low, mid);\n\t\t\tcur.right = new Node(0, mid + 1, cur.high);\n\t\t}\n\t\tupdateCore(left, right, cur.left, newVal);\n\t\tupdateCore(left, right, cur.right, newVal);\n\n\t\tcur.val = merge(cur.left.val, cur.right.val);\n\t}\n\n\tprivate void execute(Node cur, int update) {\n\t\t// Apply the udpate.\n\t\tcur.val = merge(cur.val, update);\n\t\tif (cur.low != cur.high) {\n\t\t\t// Propagate the update to children.\n\t\t\tif (cur.left == null) {\n\t\t\t\tint mid = getMid(cur.low, cur.high);\n\t\t\t\tcur.left = new Node(0, cur.low, mid);\n\t\t\t\tcur.right = new Node(0, mid + 1, cur.high);\n\t\t\t}\n\t\t\tcur.left.lazyVal = merge(cur.left.lazyVal, update);\n\t\t\tcur.right.lazyVal = merge(cur.right.lazyVal, update);\n\t\t}\n\t}\n\n\tprivate int merge(int x, int y) {\n\t\treturn Math.max(x, y);\n\t}\n\n\tprivate int getMid(int left, int right) {\n\t\treturn left + (right - left) / 2;\n\t}\n\n\tstatic class Node {\n\t\t// The value for range [low ... high].\n\t\tpublic int val;\n\t\tpublic int low;\n\t\tpublic int high;\n\t\t// The lazy update yet to apply.\n\t\tpublic int lazyVal;\n\t\tpublic Node left = null;\n\t\tpublic Node right = null;\n\n\t\tpublic Node(int val, int low, int high) {\n\t\t\tthis.val = val;\n\t\t\tthis.low = low;\n\t\t\tthis.high = high;\n\t\t\tthis.lazyVal = 0;\n\t\t}\n\t}\n}\n```\n\n## Coordinates compression\nExample: [1,2,6] -> [0,1,2]\n![image](https://assets.leetcode.com/users/images/b79b1f41-eed8-4e61-9151-0f1de5d90c6d_1615007285.740065.png)\n\n```java\nMap<Integer, Integer> compressCoord(int[][] positions) {\n\tSet<Integer> points = new HashSet<>();\n\tfor (int[] pos : positions) {\n\t\tpoints.add(pos[0]);\n\t\tpoints.add(pos[0] + pos[1] - 1);\n\t}\n\n\tList<Integer> pointList = new ArrayList<>(points);\n\tCollections.sort(pointList);\n\n\tMap<Integer, Integer> coords = new HashMap<>();\n\tfor (int i = pointList.size() - 1; i >= 0; --i) {\n\t\tcoords.put(pointList.get(i), i);\n\t}\n\n\treturn coords;\n}\n```\n\n## Solution\nPut together, `SegmentTree` can be either of above.\n```java\npublic List<Integer> fallingSquares(int[][] positions) {\n\tMap<Integer, Integer> coords = compressCoord(positions);\n\n\tSegmentTree st = new SegmentTree(coords.size());\n\tList<Integer> ans = new ArrayList<>();\n\n\tint max = 0;\n\tfor (int[] pos : positions) {\n\t\tint left = coords.get(pos[0]);\n\t\tint right = coords.get(pos[0] + pos[1] - 1);\n\t\tint height = st.query(left, right) + pos[1];\n\t\tst.update(left, right, height);\n\n\t\tmax = Math.max(max, height);\n\t\tans.add(max);\n\t}\n\n\treturn ans;\n}\n```\n
[]