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.