Segment Tree Min/Max Lazy Add

Problem

Support range addition and min/max queries with a segment tree.

nums is the initial array. queries is a list of ["add", l, r, val] or ["query", l, r] (returns [minimum, maximum]). A lazy value per node defers additions to children until they are needed.

Return the list of query results.

Hint

Adding a constant to a whole segment shifts its minimum and maximum by the same amount.

Test cases

case 1

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

expected: [[4,8],[7,8]]

case 2

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

expected: [[5,5],[2,2]]

case 3

in: [[0,0,0],[["add",1,2,7],["query",0,2]]]

expected: [[0,7]]

case 4

in: [[1,2,3,4],[["add",0,3,1],["add",1,1,-10],["query",0,3]]]

expected: [[-7,5]]

case 5

in: [[],[]]

expected: []

Starter codePython

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

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