Fenwick Range Update Point Query

Problem

Support range additions and point queries with a Fenwick tree over a difference array.

nums is the initial array. queries is a list of ["add", l, r, val] (add val to nums[l..r]) or ["point", i] (current value at i). A range add becomes two point updates on the underlying binary indexed tree, and a point query is a prefix sum of differences.

Return the list of point-query results.

Hint

Storing the difference array in a BIT turns a range add into two point adds.

Test cases

case 1

in: [[1,2,3],[["add",0,1,5],["point",0],["point",1],["point",2],["add",1,2,-2],["point",2]]]

expected: [6,7,3,1]

case 2

in: [[5],[["point",0],["add",0,0,2],["point",0]]]

expected: [5,7]

case 3

in: [[0,0,0,0],[["add",1,3,4],["point",0],["point",2]]]

expected: [0,4]

case 4

in: [[1,1],[["add",0,1,0],["point",1]]]

expected: [1]

Starter codePython

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

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