Range Sum Query - Mutable

Problem

Support point updates and inclusive range sum queries on a list of integers. Operations are [1, index, value] to set an element and [2, left, right] to query the sum, and the results of queries are returned in order.

Use a Fenwick tree so both updates and queries take O(log n). An empty operation list returns an empty list.

Hint

Update the tree with the difference between the new and old values.

Test cases

case 1

in: [[1,3,5],[[2,0,2],[1,1,2],[2,0,2]]]

expected: [9,8]

case 2

in: [[1],[[2,0,0],[1,0,5],[2,0,0]]]

expected: [1,5]

case 3

in: [[],[]]

expected: []

case 4

in: [[1,2,3,4],[[2,1,3],[1,3,0],[2,0,3]]]

expected: [9,6]

case 5

in: [[0,0,0],[[1,1,7],[2,1,1]]]

expected: [7]

Starter codePython

def range_sum_mutable(nums, operations):
    # Your code here
    pass

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