Published by Dimitris Kougioumtzis · Updated
Build the range-query structure and answer an inclusive query. Optionally set one array value before querying.
Store aggregates for recursively split intervals; queries combine covered nodes and point updates repair only ancestor sums.
When to use Segment tree range sum
Dynamic interval sums.
Choosing an alternative
Fenwick trees are compact for sums; sparse tables favor immutable minima.
Worked example: input and state changes
Example input
1,2,3,4,5 | 1,4 | 2,8
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: Leaves contain the input values.
State at this checkpoint
{ "values": [ 0, 0, 0, 0, 1, 2, 3, 4, 5 ], "active": [], "kind": "graph", "tree": true, "visited": [], "chosen": [] }Step 3: Combine children into internal node 2.
State at this checkpoint
{ "values": [ 0, 10, 5, 9, 1, 2, 3, 4, 5 ], "active": [ 1 ], "kind": "graph", "tree": true, "visited": [], "chosen": [] }Step 5: Set leaf for input index 2.
State at this checkpoint
{ "values": [ 15, 10, 5, 9, 1, 2, 8, 4, 5 ], "active": [ 6 ], "kind": "graph", "tree": true, "visited": [], "chosen": [] }Step 8: Include node 3; subtotal 10.
State at this checkpoint
{ "values": [ 20, 10, 10, 9, 1, 2, 8, 4, 5 ], "active": [ 2 ], "kind": "graph", "tree": true, "visited": [], "chosen": [] }Step 10: Range sum [1,4] = 19.
State at this checkpoint
{ "values": [ 20, 10, 10, 9, 1, 2, 8, 4, 5 ], "active": [], "kind": "graph", "tree": true, "visited": [], "chosen": [], "result": 19 }
Expected final state
Range sum [1,4] = 19.
Complexity and input bounds
Family: Trees. Time complexity: O(n) build; O(log n) update/query.
Space complexity: O(n) tree storage.
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–24 values (0–99) | left,right | optional index,newValue; indices are zero-based.
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
This entry has point updates, not lazy range updates; query endpoints are inclusive.
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 | // 1–24 values 0–99, inclusive valid left/right indices. updateIndex=-1 skips update; otherwise set a[updateIndex] to newValue (0–99). Returns sum; mutates a when updating. 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, left, right, updateIndex, newValue) { let tree = Array(256).fill(0); for (let i = 0; i < n; i++) { tree[n + i] = a[i]; } for (let i = n - 1; i > 0; i--) { tree[i] = tree[2 * i] + tree[2 * i + 1]; } if (updateIndex >= 0) { a[updateIndex] = newValue; let p = n + updateIndex; tree[p] = newValue; while (p > 1) { p >>= 1; tree[p] = tree[2 * p] + tree[2 * p + 1]; } } let l = left + n; let r = right + n; let sum = 0; while (l <= r) { if (l % 2 == 1) { sum += tree[l++]; } if (r % 2 == 0) { sum += tree[r--]; } l >>= 1; r >>= 1; } return sum; } |
Source
This primary technical article documents range sums and point updates. It is a reference implementation explanation, not an original research paper.
- Segment Tree: sum queries and updates
Algorithms for Competitive Programming contributors (online reference). Algorithm reference.