All problems
Segment Tree Lazy Propagation Range Add
Problem
Support range addition and range-sum queries with a lazy segment tree.
nums is the initial array. queries is a list of ["add", l, r, val] (add val to every element in nums[l..r]) or ["query", l, r] (sum over the inclusive range). A lazy value per node defers updates to children until they are needed.
Return the list of query results.
Hint
A pending add on a node can be applied to its whole segment in constant time.
Test cases
case 1
in: [[1,2,3,4],[["add",1,2,5],["query",0,3],["add",0,3,1],["query",1,1]]]
expected: [20,8]
case 2
in: [[5],[["query",0,0],["add",0,0,-3],["query",0,0]]]
expected: [5,2]
case 3
in: [[0,0,0],[["add",0,2,7],["query",1,2]]]
expected: [14]
case 4
in: [[1,2],[["add",1,1,10],["query",0,0],["query",1,1]]]
expected: [1,12]
case 5
in: [[],[]]
expected: []
Starter codePython
def lazy_range_add(nums, queries):
# Your code here
pass5 test cases · run your code against them in the editor