Segment Tree Range Max with Index

Problem

Support range-maximum queries that also report the leftmost index of the maximum.

nums is the initial array. queries is a list of ["query", l, r] or ["update", i, val]. Each segment-tree node stores the index of the maximum in its segment, breaking ties toward the smaller index.

Return [maximum, index] for each query.

Hint

Compare values, and on a tie keep the index that comes first.

Test cases

case 1

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

expected: [[5,1]]

case 2

in: [[1,5,3,5],[["query",1,3]]]

expected: [[5,1]]

case 3

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

expected: [[2,0]]

case 4

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

expected: [[4,1]]

case 5

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

expected: [[8,2],[5,0]]

Starter codePython

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

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