Fenwick for Range Max with Limitations

Problem

Support prefix maximum queries when values only increase, using a Fenwick tree.

nums is the initial array. queries is a list of ["increase", i, val] (set nums[i] to the larger of its current value and val) or ["max", r] (maximum of nums[0..r]). A max Fenwick tree cannot support arbitrary decreases, which is why updates are restricted to increases.

Return the list of prefix maxima.

Hint

Decreasing a value cannot be undone in a prefix-max BIT, so only increases are allowed.

Test cases

case 1

in: [[1,3,2],[["max",2],["increase",0,5],["max",2],["max",0]]]

expected: [3,5,5]

case 2

in: [[0],[["max",0],["increase",0,4],["max",0]]]

expected: [0,4]

case 3

in: [[1,2,3],[["increase",1,0],["max",2]]]

expected: [3]

case 4

in: [[5,1],[["max",1],["increase",0,2],["max",1]]]

expected: [5,5]

Starter codePython

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

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