All problems
Sqrt Decomposition with Lazy Blocks
Problem
Support range addition and range sums with square-root decomposition and lazy blocks.
nums is the initial array. queries is a list of ["add", l, r, val] or ["query", l, r] (inclusive sum). Partial blocks are updated elementwise while whole blocks carry a lazy offset.
Return the list of query results.
Hint
A partial block needs its elements updated, but a fully covered block only bumps its lazy offset.
Test cases
case 1
in: [[1,2,3,4,5],[["add",0,4,1],["query",0,4],["add",1,2,10],["query",1,3]]]
expected: [20,32]
case 2
in: [[5],[["query",0,0],["add",0,0,-2],["query",0,0]]]
expected: [5,3]
case 3
in: [[],[]]
expected: []
case 4
in: [[0,0,0],[["add",0,2,7],["query",0,2]]]
expected: [21]
case 5
in: [[1,2,3,4],[["add",1,1,10],["query",0,3],["query",1,1]]]
expected: [20,12]
Starter codePython
def sqrt_lazy_range_add(nums, queries):
# Your code here
pass5 test cases · run your code against them in the editor