Published by Dimitris Kougioumtzis · Updated
Store segment sums with pending range-add tags. Apply full-cover updates without descending, and push tags only when a later update or query needs the children.
Apply a full-cover range-add directly to a node sum and retain a lazy tag. Before descending into a partial overlap, push that tag into both children. Pull child sums back after a partial update.
When to use Segment tree lazy range updates
Range-add and range-sum queries when many intervals overlap.
Choosing an alternative
The point-update segment-tree view descends to individual leaves. Lazy propagation avoids touching every leaf in a fully covered interval.
Worked example: input and state changes
Example input
1,2,3,4,5,6,7,8 | 0,7,5;2,4,-3 | 3,6
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: First 32 cells are indexed segment sums; next 32 are lazy tags. Index 0 is unused in each half.
State at this checkpoint
{ "values": [ 0, 36, 10, 26, 3, 7, 11, 15, 1, 2, 3, 4, 5, 6, 7, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], "active": [], "kind": "matrix", "columns": 8, "blocked": [ 0, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63 ] }Step 4: Add -3 to all entries in [2,3]; retain a lazy tag at node 5.
State at this checkpoint
{ "values": [ 0, 76, 30, 46, 13, 11, 11, 15, 1, 2, 3, 4, 5, 6, 7, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 5, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], "active": [ 5, 37 ], "kind": "matrix", "columns": 8, "blocked": [ 0, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63 ] }Step 9: Pull child sums back into node 6.
State at this checkpoint
{ "values": [ 0, 76, 24, 46, 13, 11, 18, 25, 1, 2, 3, 4, 7, 11, 7, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 2, 0, 5, 0, 0, 0, 0, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], "active": [ 6 ], "kind": "matrix", "columns": 8, "blocked": [ 0, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63 ] }Step 13: Take sum 6 from node 11, interval [3,3].
State at this checkpoint
{ "values": [ 0, 67, 24, 43, 13, 11, 18, 25, 1, 2, 5, 6, 7, 11, 7, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 5, 0, 0, 2, 2, 2, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], "active": [ 11 ], "kind": "matrix", "columns": 8, "blocked": [ 0, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63 ] }Step 17: Range sum [3,6] = 36.
State at this checkpoint
{ "values": [ 0, 67, 24, 43, 13, 11, 18, 25, 1, 2, 5, 6, 7, 11, 12, 13, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 2, 2, 2, 5, 5, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ], "active": [], "kind": "matrix", "columns": 8, "blocked": [ 0, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63 ], "result": 36 }
Expected final state
Range sum [3,6] = 36.
Complexity and input bounds
Family: Trees. Time complexity: O(log n) per update/query.
Implementation detail: The matrix displays 32 indexed sums followed by 32 lazy tags. Inputs have at most eight values and four signed range-add updates. Negative query sums are valid. Downloads write the state after the query has pushed any tags needed for its answer.
Space complexity: O(n) conceptual tree and traversal storage; fixed portable scratch buffers and recorded frames are described by the bounded contract.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
1..8 values (0..99) | zero to four l,r,delta updates separated by semicolons | query l,r. Delta -9..9; inclusive valid ranges.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Scale a range-add by the segment length when changing its sum. Push tags before partial queries too, and clear the parent tag. Zero padding must not become part of a valid input range.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | // Range-add/range-sum lazy segment tree: n 1..8 initial values 0..99; updates 0..4; each from[i]..to[i] and ql..qr is an inclusive valid range, deltas -9..9. Returns query sum (negative sums are valid). Output capacity at least 64: first 32 indexed tree sums, next 32 lazy tags; index 0 unused in each half, inactive cells zero. Leaves are padded with zero to the next power of two. Output records state after the query has pushed any needed tags. O(n) build, O(log n) per update/query, O(n) auxiliary space. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(a, n, from, to, delta, updates, ql, qr, output) { let tree = Array(256).fill(0); let lazy = Array(256).fill(0); let nodes = Array(256).fill(0); let lows = Array(256).fill(0); let highs = Array(256).fill(0); let phase = Array(256).fill(0); let size = 1; let answer = 0; let top = 0; let u = 0; let l = 0; let r = 0; let mid = 0; let first = 0; let last = 0; let amount = 0; while (size < n) { size *= 2; } for (let i = 0; i < n; i++) { tree[size + i] = a[i]; } for (let i = size - 1; i > 0; i--) { tree[i] = tree[2 * i] + tree[2 * i + 1]; } for (let operation = 0; operation <= updates; operation++) { first = ql; last = qr; amount = 0; if (operation < updates) { first = from[operation]; last = to[operation]; amount = delta[operation]; } top = 1; nodes[0] = 1; lows[0] = 0; highs[0] = size - 1; phase[0] = 0; while (top > 0) { top--; u = nodes[top]; l = lows[top]; r = highs[top]; if (phase[top] == 1) { tree[u] = tree[2 * u] + tree[2 * u + 1]; continue; } if (last < l || r < first) { continue; } if (first <= l && r <= last) { if (operation == updates) { answer += tree[u]; } else { tree[u] += amount * (r - l + 1); lazy[u] += amount; } continue; } mid = (l + r) >> 1; if (lazy[u] != 0) { tree[2 * u] += lazy[u] * (mid - l + 1); lazy[2 * u] += lazy[u]; tree[2 * u + 1] += lazy[u] * (r - mid); lazy[2 * u + 1] += lazy[u]; lazy[u] = 0; } if (operation < updates) { nodes[top] = u; lows[top] = l; highs[top] = r; phase[top++] = 1; } nodes[top] = 2 * u + 1; lows[top] = mid + 1; highs[top] = r; phase[top++] = 0; nodes[top] = 2 * u; lows[top] = l; highs[top] = mid; phase[top++] = 0; } } for (let i = 0; i < 32; i++) { output[i] = tree[i]; output[32 + i] = lazy[i]; } return answer; } |
Source
The authored technical reference includes lazy range updates. It is an implementation explanation, not an attribution to an original research paper.
- Segment Tree: sum queries and updates
Algorithms for Competitive Programming contributors (online reference). Algorithm reference.