Segment tree
The root holds the sum of everything. Its children hold the sums of each half, their children the quarters, down to single values. Any range can be built from a few of these whole pieces, so a range sum needs about log n nodes instead of adding up every value.
empty tree
Build a tree of sums over 8 values, then use it to add up positions 2 to 5.
1function build(a, node, lo, hi) {2 if (lo === hi) return (tree[node] = a[lo]);3 const mid = Math.floor((lo + hi) / 2);4 return (tree[node] = build(a, 2 * node, lo, mid) + build(a, 2 * node + 1, mid + 1, hi));5}67function query(node, lo, hi, l, r) {8 if (r < lo || hi < l) return 0;9 if (l <= lo && hi <= r) return tree[node];10 const mid = Math.floor((lo + hi) / 2);11 return query(2 * node, lo, mid, l, r) + query(2 * node + 1, mid + 1, hi, l, r);12}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | 1 | a query for the whole array: the root already has it |
| average | log n | per query, or per update of one value |
| worst | log n | at most about four nodes per level |
| space | n | about 2n nodes; arrays usually reserve 4n |
Where it breaks
- No updates, no need. If the values never change, a plain prefix-sum array answers any range sum in one subtraction. The segment tree is worth it when values change between queries: one update fixes only the log n sums above that value.
- Sizing the array. Stored in an array with node k's children at 2k and 2k + 1, the tree can need up to 4n slots for awkward sizes, not 2n. Allocating too little is a classic bug.
- Not just sums. Swap + for min or max and the same tree answers range minimum or maximum. Anything that combines two halves into one answer works.