subroute.
Advanced11 min readlive prototype

Segment Tree

A tree of ranges over an array. Answer 'sum/min/max of indices l..r' and update any element, both in O(log n) — the competitive-programmer's range engine.

Overview

What this concept solves

A segment tree turns any associative aggregation into a O(log n) range query. Build a complete binary tree over an array of n elements. Each leaf stores one element. Each internal node stores the combined aggregate — sum, minimum, maximum, GCD, or anything else you can merge — for the contiguous sub-array its subtree covers. The root covers [0..n-1]; the two children split that range in half, recursively, down to single-element leaves. With O(n) space (typically a flat array of size 4n) you get every range query you'll ever need, answered in O(log n) time.

The query algorithm is driven by three overlap cases between the query range [l..r] and the node's range [nl..nr]. DISJOINT: if [nl..nr] and [l..r] don't overlap at all, return the identity element immediately — this entire subtree is irrelevant. FULLY INSIDE: if [nl..nr] is completely contained within [l..r], return the node's stored value without recursing — this node's aggregate is exact. PARTIAL: if they partially overlap, recurse into both children and combine their answers. The magic is that at each level of the tree, at most four nodes are in the partial state; every other node is either fully inside or disjoint. This bounds the work to O(log n) even when the query range is huge.

Point updates are the mirror image. Walk from root to the target leaf, following the half that contains the index. Change the leaf's value, then on the way back up recompute each ancestor from its two children. The path is O(log n) nodes long, so the total update cost is O(log n). This is the essential trade-off versus a plain prefix-sum array: prefix sums answer range-sum queries in O(1) but require O(n) to rebuild after any update. The segment tree sacrifices a log factor on queries to make updates equally fast — a critical property for any workload that mixes reads and writes on live data.

Mechanics

How it works

Build — O(n) time, O(n) space

  1. Allocate a flat array tree of size 4n (a safe upper bound). Node 1 is the root; node i's children are 2i and 2i+1.
  2. Recursively build: build(node, nl, nr) — if nl === nr, set tree[node] = a[nl] (leaf). Otherwise, split at mid = ⌊(nl+nr)/2⌋, recurse on both children, then set tree[node] = combine(tree[2·node], tree[2·node+1]).
  3. The recursion bottoms out at n leaves and does O(1) work per internal node, so total build time is O(n).

Range query — three overlap cases

  1. DISJOINT (nr < l or r < nl): the node's range is entirely outside the query range. Return the identity element (0 for sum, +∞ for min, -∞ for max). Do not recurse.
  2. FULLY INSIDE (l ≤ nl and nr ≤ r): the node's range is completely covered by the query range. Return tree[node] directly. Do not recurse.
  3. PARTIAL: the ranges overlap but neither contains the other. Split at mid, recurse on both children, return combine(left_result, right_result).

Point update — O(log n)

  1. Recurse from root to the target leaf, going left if idx ≤ mid, right otherwise.
  2. At the leaf (nl === nr === idx), set tree[node] = newValue.
  3. On the way back up, recompute each ancestor: tree[node] = combine(tree[2·node], tree[2·node+1]).

Associativity is the only requirement

The combine function must be associative: combine(a, combine(b, c)) === combine(combine(a, b), c). It does not need to be commutative (though sum/min/max happen to be). This is why segment trees handle GCD, bitwise AND/OR, matrix multiplication over ranges, and even custom merge functions — anything that can be split and rejoined in any bracket order works.

Lazy propagation for range updates

A point update is O(log n), but updating every element in a range [l..r] naively costs O(n log n). Lazy propagation fixes this: instead of pushing a range update all the way to the leaves immediately, store a pending tag at the highest fully-covered node and propagate it downward only when that node is visited next. This keeps both range updates and range queries at O(log n). Lazy propagation is the standard extension for problems like 'add 5 to every element in [3..7], then query the sum of [1..8].'

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

About this simulation

A segment tree built over the default array a = [3, 2, 5, 1, 4, 6, 2, 7]. Toggle between Sum, Min, and Max modes to swap the aggregate. Enter lo / hi and press Query to fire a range query — nodes light up yellow (visiting), green (fully inside, result taken), or dim (disjoint, skipped). Enter idx / value and press Update to move a leaf and watch the combines ripple back up the path. Three demo buttons replay: "Query full range [1..8]", "Query single element [3..3]", and "Set a5 = 10, then query [3..6]". The stats bar shows n, height, the current result, and nodes visited.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Two range queries — full cover vs. single element

Click "Query full range [1..8]". Watch the root (covering [1..8]) immediately go green — it's FULLY INSIDE the query range, so the result is taken without a single recursion into children. The stats bar shows visited = 1. Now click "Query single element [3..3]" and watch the opposite: the tree descends all the way to the leaf at index 3, and every sibling node along the path goes dim (DISJOINT). Notice how nodes at each level split the decision — left child is disjoint or fully inside, right child continues narrowing. This is the three-overlap-case engine: at most four nodes are in the PARTIAL state at any level, which is why the visited count is bounded by O(log n) even for arbitrary ranges.

try 02

Point update then range query

Click "Set a5 = 10, then query [3..6]". First, the update animation highlights the root-to-leaf path for index 5 in yellow as it descends; when it hits the leaf it changes the stored value, then the green recompute sweeps back up — each ancestor recalculates from its two children. Then the query fires on [3..6]: compare the result to what you'd get without the update (the original array gives sum=1+4+6+2=13 for indices 3-6; after setting a5=10 the result should be 1+10+6+2=19 for sum mode). Toggle to Min and re-run the demo — the update propagation looks identical, but the merge logic changes and so does the answer.

try 03

Toggle Sum / Min / Max and re-query

Enter lo=2, hi=6 in the query inputs and press Query in Sum mode — note the result. Now switch to Min and press Query again (the range stays). The visited node pattern is identical — the same three-overlap-case traversal — but the green nodes now return their minimum instead of their sum, and the combines along partial nodes take Math.min instead of +. Switch to Max and repeat. This is the segment tree's generality: one traversal algorithm, swappable combine function. The only thing that changes between the three modes is what combine(a, b) returns and what identity element is returned for DISJOINT nodes.

try 04

Free play — break it yourself

Try entering a query range that's just one element wide: lo=hi=4. Count the visited nodes — it should equal the tree height (roughly log₂ 8 = 3 internal levels plus the leaf). Now enter the widest possible range lo=1, hi=8 — visited should be 1 (root is fully inside). Notice the worst case is a range like lo=2, hi=7 — count visited and see how the partial nodes at each level multiply. Finally, hammer the Update button repeatedly with different index/value pairs and watch the path light up each time. Can you craft a sequence of updates and queries that produces a surprising result? Try setting all values to the same number, then querying Min — the tree should collapse to that value everywhere.

In practice

When to use it — and what you give up

Reach for a segment tree when

  • You need range queries and point updates on the same array — the core sweet spot. Any workload that mixes 'read a range aggregate' with 'change one element' is a segment tree problem.
  • The aggregate is not just a sum — range minimum, range maximum, range GCD, range bitwise OR. Fenwick trees natively support only prefix sums (and, with tricks, range sums); segment trees support any associative operation.
  • You need range updates in addition to range queries — add lazy propagation and both stay O(log n).
  • You need to query and update offline on static-size arrays — segment trees work on arrays that don't grow or shrink (for dynamic sizes, consider a dynamic segment tree or a balanced BST).
  • Competitive programming problems that mention 'range query' and 'update' together almost always call for a segment tree.

When to consider the alternatives

  • Prefix-sum array: if your array is read-only after initial build, prefix sums answer range-sum queries in O(1) with O(n) space and trivial code. No updates allowed.
  • Fenwick tree (Binary Indexed Tree): if you need only point updates and prefix sums (or range sums), the Fenwick tree has the same O(log n) complexity but uses ~2× less memory, has a smaller constant, and fits in ~10 lines. Pick Fenwick for sum-only workloads; pick segment tree when the operation is anything else or when you need lazy range updates.
  • Sparse table: for static range-minimum / range-maximum queries with O(1) query time and O(n log n) build — but no updates at all.
  • Sqrt decomposition: simpler to implement (no recursion), handles a wider variety of non-associative queries, but O(√n) per operation instead of O(log n).

Pros

  • O(log n) range queries for any associative operation — sum, min, max, GCD, bitwise ops, matrix products, custom merges all fit the same template.
  • O(log n) point updates — unlike prefix-sum arrays which need O(n) to rebuild after a change.
  • O(n) build time — the full tree is constructed in a single O(n) bottom-up or top-down pass.
  • Lazy propagation extends it to O(log n) range updates — 'add 5 to [3..7]' costs the same as a single point update.
  • Flat-array implementation — storing the tree in a 1-indexed array of size 4n is cache-friendly and avoids pointer overhead. No dynamic allocation needed.

Cons

  • ~4× memory overhead — the tree array needs up to 4n nodes. A Fenwick tree on the same data needs exactly n+1 cells.
  • Larger constant than Fenwick — recursive calls, range comparisons, and combine logic add up. For sum-only workloads with tight time limits, Fenwick wins on raw speed.
  • Non-trivial to implement correctly — off-by-one errors in range splits, wrong identity elements, and forgetting to push lazy tags down before recursing are all common bugs.
  • Lazy propagation multiplies complexity — the basic structure is ~30 lines; full lazy propagation can triple that, and each new operation type needs a custom 'tag compose' function.
  • Static size — a standard segment tree is built over a fixed n. Handling insertions or deletions requires a dynamic/implicit segment tree, which is substantially more complex.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

segment-tree.ts
// Recursive segment tree supporting sum / min / max via a swappable combine.
// tree[] is 1-indexed; node i's children are 2i and 2i+1.
// Build is O(n); query and point-update are O(log n).

type Combine = (a: number, b: number) => number;

class SegmentTree {
  private tree: number[];
  private n: number;
  private combine: Combine;
  private identity: number;

  constructor(a: number[], combine: Combine, identity: number) {
    this.n = a.length;
    this.combine = combine;
    this.identity = identity;
    this.tree = new Array(4 * this.n).fill(identity);
    this.build(a, 1, 0, this.n - 1);
  }

  private build(a: number[], node: number, nl: number, nr: number): void {
    if (nl === nr) { this.tree[node] = a[nl]; return; }
    const mid = (nl + nr) >> 1;
    this.build(a, 2 * node,     nl,      mid);
    this.build(a, 2 * node + 1, mid + 1, nr);
    this.tree[node] = this.combine(this.tree[2 * node], this.tree[2 * node + 1]);
  }

  query(l: number, r: number, node = 1, nl = 0, nr = this.n - 1): number {
    if (nr < l || r < nl) return this.identity;          // DISJOINT
    if (l <= nl && nr <= r) return this.tree[node];      // FULLY INSIDE
    const mid = (nl + nr) >> 1;                          // PARTIAL — recurse
    return this.combine(
      this.query(l, r, 2 * node,     nl,      mid),
      this.query(l, r, 2 * node + 1, mid + 1, nr),
    );
  }

  update(idx: number, val: number, node = 1, nl = 0, nr = this.n - 1): void {
    if (nl === nr) { this.tree[node] = val; return; }    // leaf — set
    const mid = (nl + nr) >> 1;
    if (idx <= mid) this.update(idx, val, 2 * node,     nl,      mid);
    else            this.update(idx, val, 2 * node + 1, mid + 1, nr);
    this.tree[node] = this.combine(this.tree[2 * node], this.tree[2 * node + 1]);
  }
}

// Usage:
const a = [3, 2, 5, 1, 4, 6, 2, 7];
const sumTree = new SegmentTree(a, (x, y) => x + y, 0);
const minTree = new SegmentTree(a, Math.min,          Infinity);
const maxTree = new SegmentTree(a, Math.max,         -Infinity);

console.log(sumTree.query(2, 5)); // sum of a[2..5] = 5+1+4+6 = 16
sumTree.update(4, 10);            // set a[4] = 10
console.log(sumTree.query(2, 5)); // 5+1+10+6 = 22

References & further reading

7 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

A range query on a segment tree visits at most O(log n) nodes even when the query range spans nearly the whole array. Why?

question 02 / 03

Which of the following aggregate functions CANNOT be supported by a standard segment tree?

question 03 / 03

When should you choose a Fenwick tree (Binary Indexed Tree) over a segment tree?

0/3 answered

Was this concept helpful?

Tell us what worked, or what to improve. We read every note.

Back to Trees