Kotlin - Segment Tree, Binary Tree Implementation, with Lazy Propagation
\nclass Solution {\n    fun fallingSquares(positions: Array<IntArray>): List<Int> {\n        val root = SegmentTree()\n        \n        val ans = mutableListOf
```\nclass Solution {\n    fun fallingSquares(positions: Array<IntArray>): List<Int> {\n        val root = SegmentTree()\n        \n        val ans = mutableListOf<Int>()\n        var tallest = 0\n        \n        for((start, sideLen) in positions){\n            val end = start + sideLen\n            \n            val height = root.query(start, end - 1) + sideLen\n        \n            root.update(start, end - 1, height)\n            tallest = maxOf(tallest, height)\n            \n            ans.add(tallest)\n        }\n        \n        return ans\n    }\n    \n    private class SegmentTree {\n        private companion object {\n            private const val RANGE = 1e9.toInt() + 1\n        }\n\n        private val root = SegmentTreeNode(0, RANGE)\n\n        fun update(rangeLo: Int, rangeHi: Int, value: Int) = update(rangeLo, rangeHi, value, root)\n        fun query(rangeLo: Int, rangeHi: Int) = query(rangeLo, rangeHi, root)\n\n        private fun update(rangeLo: Int, rangeHi: Int, value: Int, node: SegmentTreeNode?) {\n            if (node == null) return\n            if (rangeLo <= node.lo && node.hi <= rangeHi) {\n                node.lazy += value\n            }\n\n            pushDown(node)\n\n            // complete overlap or no overlap at all\n            if (rangeLo <= node.lo && node.hi <= rangeHi || rangeHi < node.lo || rangeLo > node.hi) return\n\n            update(rangeLo, rangeHi, value, node.left)\n            update(rangeLo, rangeHi, value, node.right)\n\n            node.max = maxOf(node.left!!.max, node.right!!.max)\n        }\n\n        private fun query(rangeLo: Int, rangeHi: Int, node: SegmentTreeNode?): Int {\n            if (node == null) return 0\n            pushDown(node)\n\n            // no overlap\n            if (rangeLo > node.hi || rangeHi < node.lo) return 0\n\n            // complete overlap\n            if (rangeLo <= node.lo && node.hi <= rangeHi) return node.max\n\n            val leftMax = query(rangeLo, rangeHi, node.left)\n            val rightMax = query(rangeLo, rangeHi, node.right)\n\n            return maxOf(leftMax, rightMax)\n        }\n\n        private fun pushDown(node: SegmentTreeNode) {\n            node.max = maxOf(node.max, node.lazy)\n\n            if (node.lo != node.hi) {\n                val mid = node.lo + (node.hi - node.lo) / 2\n\n                if (node.left == null) {\n                    node.left = SegmentTreeNode(node.lo, mid)\n                }\n\n                if (node.right == null) {\n                    node.right = SegmentTreeNode(mid + 1, node.hi)\n                }\n                \n                node.left!!.lazy = maxOf(node.left!!.lazy, node.lazy)\n                node.right!!.lazy = maxOf(node.right!!.lazy, node.lazy)\n            }\n\n            node.lazy = 0\n        }\n    }\n\n    private data class SegmentTreeNode(val lo: Int,\n                                       val hi: Int,\n                                       var max: Int = 0,\n                                       var lazy: Int = 0,\n                                       var left: SegmentTreeNode? = null,\n                                       var right: SegmentTreeNode? = null)\n}\n```\n\n\nWith range compressed:\n```\nclass Solution {\n    fun fallingSquares(positions: Array<IntArray>): List<Int> {        \n        val ranksMap = compressRange(positions)\n        \n        val root = SegmentTree()\n        \n        val ans = mutableListOf<Int>()\n        var tallest = 0\n        \n        for((start, sideLen) in positions){\n            val end = start + sideLen - 1\n            \n            val rangeLo = ranksMap[start]!!\n            val rangeHi = ranksMap[end]!!\n            \n            val height = root.query(rangeLo, rangeHi) + sideLen\n        \n            root.update(rangeLo, rangeHi, height)\n            tallest = maxOf(tallest, height)\n            \n            ans.add(tallest)\n        }\n        \n        return ans\n    }\n    \n    private fun compressRange(positions: Array<IntArray>): HashMap<Int, Int>{\n        val coordSet = HashSet<Int>()\n        for((start, sideLen) in positions){\n            val end = start + sideLen - 1\n            coordSet.add(start)\n            coordSet.add(end)\n        }\n        val sortedCoords = coordSet.toMutableList().also{ it.sort() }\n        \n        var ranks = 1\n        val ranksMap = HashMap<Int, Int>()\n        for(coord in sortedCoords) ranksMap[coord] = ranks++\n        \n        return ranksMap\n    }\n    \n    private class SegmentTree {\n        private companion object {\n            private const val RANGE = 1e9.toInt() + 1\n        }\n\n        private val root = SegmentTreeNode(0, RANGE)\n\n        fun update(rangeLo: Int, rangeHi: Int, value: Int) = update(rangeLo, rangeHi, value, root)\n        fun query(rangeLo: Int, rangeHi: Int) = query(rangeLo, rangeHi, root)\n\n        private fun update(rangeLo: Int, rangeHi: Int, value: Int, node: SegmentTreeNode?) {\n            if (node == null) return\n            if (rangeLo <= node.lo && node.hi <= rangeHi) {\n                node.lazy += value\n            }\n\n            pushDown(node)\n\n            // complete overlap or no overlap at all\n            if (rangeLo <= node.lo && node.hi <= rangeHi || rangeHi < node.lo || rangeLo > node.hi) return\n\n            update(rangeLo, rangeHi, value, node.left)\n            update(rangeLo, rangeHi, value, node.right)\n\n            node.max = maxOf(node.left!!.max, node.right!!.max)\n        }\n\n        private fun query(rangeLo: Int, rangeHi: Int, node: SegmentTreeNode?): Int {\n            if (node == null) return 0\n            pushDown(node)\n\n            // no overlap\n            if (rangeLo > node.hi || rangeHi < node.lo) return 0\n\n            // complete overlap\n            if (rangeLo <= node.lo && node.hi <= rangeHi) return node.max\n\n            val leftMax = query(rangeLo, rangeHi, node.left)\n            val rightMax = query(rangeLo, rangeHi, node.right)\n\n            return maxOf(leftMax, rightMax)\n        }\n\n        private fun pushDown(node: SegmentTreeNode) {\n            node.max = maxOf(node.max, node.lazy)\n\n            if (node.lo != node.hi) {\n                val mid = node.lo + (node.hi - node.lo) / 2\n\n                if (node.left == null) {\n                    node.left = SegmentTreeNode(node.lo, mid)\n                }\n\n                if (node.right == null) {\n                    node.right = SegmentTreeNode(mid + 1, node.hi)\n                }\n                \n                node.left!!.lazy = maxOf(node.left!!.lazy, node.lazy)\n                node.right!!.lazy = maxOf(node.right!!.lazy, node.lazy)\n            }\n\n            node.lazy = 0\n        }\n    }\n\n    private data class SegmentTreeNode(val lo: Int,\n                                       val hi: Int,\n                                       var max: Int = 0,\n                                       var lazy: Int = 0,\n                                       var left: SegmentTreeNode? = null,\n                                       var right: SegmentTreeNode? = null)\n}\n```
['Kotlin']