Block Decomposition for Updates

So far you've seen point updates. What about range updates? For "add $v$ to all elements in $[l, r]$", use lazy blocks:

$1.$ For complete blocks in $[l, r]$: add $v$ to a $blockAdd$ array

$2.$ For partial blocks (tails): update individual elements Queries now add $blockAdd[block]$ to each accessed element. You get $O(\sqrt{n})$ for both range updates and point queries. The technique is called "sqrt decomposition with lazy propagation."