Segment Tree Lazy Assignment

Problem

Support range assignment and range-sum queries with a lazy segment tree.

nums is the initial array. queries is a list of ["assign", l, r, val] (set every element in nums[l..r] to val) or ["query", l, r] (inclusive sum). A None in the lazy array means there is no pending assignment for that node.

Return the list of query results.

Hint

An assignment overwrites any older pending assignment, so one lazy value per node suffices.

Test cases

case 1

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

expected: [17,10]

case 2

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

expected: [5,2]

case 3

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

expected: [14]

case 4

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

expected: [9,2]

case 5

in: [[],[]]

expected: []

Starter codePython

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

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