Fenwick Tree Prefix Sum

Problem

Support point updates and prefix-sum queries with a Fenwick tree (binary indexed tree).

nums is the initial array. queries is a list of ["update", i, delta] (add delta to nums[i]), ["prefix", i] (sum of nums[0] through nums[i] inclusive), or ["range", l, r] (sum of nums[l] through nums[r] inclusive), using 0-based indices.

Return the list of prefix and range results in order.

Hint

Update climbs i += i & -i; prefix query climbs i -= i & -i on the 1-based tree.

Test cases

case 1

in: [[1,2,3,4,5],[["prefix",2],["update",1,10],["prefix",2],["range",1,3]]]

expected: [6,16,19]

case 2

in: [[7],[["prefix",0],["update",0,3],["prefix",0]]]

expected: [7,10]

case 3

in: [[0,0,0],[["range",0,2],["update",2,5],["range",1,2],["prefix",2]]]

expected: [0,5,5]

case 4

in: [[4,2],[["range",0,1],["update",1,-2],["prefix",1]]]

expected: [6,4]

Starter codePython

def fenwick_ops(nums, queries):
    # Your code here
    pass

4 test cases · run your code against them in the editor