Segment Tree Range Minimum

Problem

Support range-minimum queries and point updates on a list with a recursive segment tree.

nums is the initial array. queries is a list of ["query", l, r] (minimum of nums[l] through nums[r] inclusive) or ["update", i, val] (set nums[i] = val), using 0-based indices. Each node stores the minimum of its segment.

Return the list of query results in order.

Hint

Each internal node stores the minimum of its two children.

Test cases

case 1

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

expected: [1,0]

case 2

in: [[3],[["query",0,0]]]

expected: [3]

case 3

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

expected: [4]

case 4

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

expected: [7,-5]

case 5

in: [[],[]]

expected: []

Starter codePython

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

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