Fenwick Range Add and Range Sum

Problem

Support range additions and range sums with two Fenwick trees over the difference array. nums is the initial array. queries is a list of ["add", l, r, val] (add val to nums[l..r] inclusive) or ["sum", l, r] (sum of nums[l..r]). Keeping one BIT over d[i] and another over d[i] * i makes prefix sums cost two queries. Return the sum-query results in order.

Hint

With d the difference array, prefix_sum(i) = (i + 1) * sum(d[0..i]) - sum(k * d[k] for k <= i).

Test cases

case 1

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

expected: [10,30,12,17]

case 2

in: [[-5,2,0,7],[["sum",0,0],["add",0,3,-3],["sum",0,3],["sum",2,2]]]

expected: [-5,-8,-3]

case 3

in: [[0],[["sum",0,0],["add",0,0,5],["sum",0,0]]]

expected: [0,5]

Starter codePython

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

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