Segment Tree with Lazy Propagation

A standard segment tree supports point updates in O(log n) and range queries in O(log n). But what about range updates: adding a value to every element in [l, r]?

The naive approach is k individual point updates, costing O(k log n). For k close to n, that is worse than just updating a raw array in O(n).

Lazy propagation brings range updates down to O(log n), matching the range query cost. It builds on a standard segment tree, using the same 1-indexed storage (root at index 1, children at 2*node and 2*node + 1) throughout this chapter.