Segment Tree Range Sum

Problem

Support range-sum queries and point updates on a list using a segment tree.

nums is the initial array. queries is a list of ["query", l, r] (sum of nums[l] through nums[r] inclusive) or ["update", i, val] (set nums[i] = val), using 0-based indices. Build the tree once, then process the queries in order.

Return the list of query results in order.

Hint

Store each node's segment range; a query splits into O(log n) fully covered segments.

Test cases

case 1

in: [[1,3,5,7,9,11],[["query",1,3],["update",1,10],["query",1,3],["query",0,5]]]

expected: [15,22,43]

case 2

in: [[5],[["query",0,0],["update",0,-3],["query",0,0]]]

expected: [5,-3]

case 3

in: [[2,4],[["query",0,1],["update",0,100],["query",0,0]]]

expected: [6,100]

case 4

in: [[0,0,0,0],[["query",0,3],["update",2,7],["query",1,2]]]

expected: [0,7]

Starter codePython

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

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