An easy level question with an interesting solution.

I’ve been watching the lessons at this Udemy class by William Fiset and one of the topics is about Fenwick Tree so I decided to find a problem that can be solved by using this datastructure.

class NumArray(nums: IntArray) {

lateinit var tree: IntArray

init {
// make nums 1-based array
tree = IntArray(nums.size + 1)
for(i in 0 until nums.size){
tree[i+1] = nums[i]
}

// construct our fenwick tree
for(i in 1 until tree.size){
val j = i + lsb(i)
if(j < tree.size){
tree[j] += tree[i]
}
}
}

private fun prefixSum(index: Int): Int {
var sum = 0
var x = index + 1
while(x > 0){
sum += tree[x]
x -= lsb(x)
}

return sum
}

private fun lsb(num: Int): Int {
return Integer.lowestOneBit(num)
}

fun sumRange(i: Int, j: Int): Int {
return prefixSum(j) -  prefixSum(i - 1)
}

}

/**
* Your NumArray object will be instantiated and called as such:
* var obj = NumArray(nums)
* var param_1 = obj.sumRange(i,j)
*/

Runtime: 256 ms, faster than 65.91% of Kotlin online submissions for Range Sum Query - Immutable.
Memory Usage: 43.9 MB, less than 100.00% of Kotlin online submissions for Range Sum Query - Immutable.


It’s not the fastest though but the solution is elegant.