:: Kotlin :: Fenwick Tree
\n\nclass Solution {\n    fun resultArray(nums: IntArray): IntArray {\n        val n = nums.size\n        val m = nums.max()!!\n\n        val arr1 = mutableList
\n```\nclass Solution {\n    fun resultArray(nums: IntArray): IntArray {\n        val n = nums.size\n        val m = nums.max()!!\n\n        val arr1 = mutableListOf<Int>()\n        val fw1 = Fenwick(m + 1)\n        val arr2 = mutableListOf<Int>()\n        val fw2 = Fenwick(m + 1)\n\n        arr1.add(nums[0])\n        fw1.update(nums[0])\n        arr2.add(nums[1])\n        fw2.update(nums[1])\n\n        for (i in 2 until n) {\n            val r1 = arr1.size - fw1.range(nums[i])\n            val r2 = arr2.size - fw2.range(nums[i])\n\n            if (r1 > r2) {\n                arr1.add(nums[i])\n                fw1.update(nums[i])\n            } else if (r1 < r2) {\n                arr2.add(nums[i])\n                fw2.update(nums[i])\n            } else if (arr2.size < arr1.size){\n                arr2.add(nums[i])\n                fw2.update(nums[i])\n            } else {\n                arr1.add(nums[i])\n                fw1.update(nums[i])\n            }\n        }\n\n        return (arr1 + arr2).toIntArray()\n    }\n}\n\nclass Fenwick {\n    val count = HashMap<Int, Int>()\n    val max: Int\n\n    constructor(m: Int) {\n        max = m\n    }\n\n    fun range(to: Int): Int{\n        var sum = 0\n        var i = to\n\n        while (i > 0) {\n            sum += count[i] ?: 0\n            i -= i and (-i)\n        }\n\n        return sum\n    }\n\n    fun update(num: Int) {\n        var i = num\n        while (i <= max) {\n            count[i] = (count[i] ?: 0) + 1\n            i += i and (-i)\n        }\n    }\n}\n```
['Kotlin']