Range Sum Query Immutable

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.

comments powered by Disqus