Segment Tree Visualizer: range queries in O(log n).

What is a segment tree?

Range queries, a thousand times.

A segment tree is a binary tree that supports range queries (sum, min, max, gcd) and point or range updates in O(log n). The structure dates to early competitive-programming literature; Jon Bentley's Programming Pearls popularised the building-blocks idea. Modern uses: histogram aggregation, time-series rollups, SQL window-frame implementation, OLAP cube stores.

Imagine an analytics dashboard that lets a user pick any time range and see the total — sales between Tuesday at 3pm and Thursday at noon, for instance. Behind the scenes you have an array with one entry per minute. The natural answer is to walk the array from index 3 to index 47 and add up the values. That is O(r − l), which on a million-element array means roughly a million operations per query. One query is fine. A thousand users sliding date pickers are not — your dashboard becomes uselessly slow.

Your first instinct, if you've seen the trick before, is the prefix-sum array: precompute one extra array where each entry is the sum of all values up to that index. Now any range sum is just prefix[hi+1] − prefix[lo] — two reads and a subtraction, regardless of how big the range is. Brilliant. But it only works for operations that have a clean inverse. Sum has subtraction. XOR is its own inverse. Count is sum-of-ones. Min, max, GCD, and most string aggregates have no inverse — there is no “subtract a min” operation. And the prefix array goes stale the moment any underlying value changes; updates force you to rebuild it from scratch in O(n).

The segment tree is what gives you both. It pre-aggregates the array at every power-of-two granularity at once. Each leaf holds one array slot. Each internal node holds the aggregate of its subtree's leaf range. The root holds the aggregate of the whole array. With this scaffolding any range query becomes a combination of at most 2 · log₂ n precomputed pieces — about forty for an array of a billion — and any single-element update touches only the log₂ n ancestors of the modified leaf. The structure works for sum, min, max, GCD, XOR, matrix product, anything associative.

Concretely: a million-element array gives a segment tree of two million slots — about 16 MB of 64-bit integers. Range sum and point update both run in around 20 comparisons each on that tree, well under a microsecond on a modern CPU. A billion-query workload that would have taken a teraflop of pointer chasing now finishes in a few seconds. The simulator above lets you click a range, watch the algorithm select the small set of pre-aggregated nodes that cover it, and update an individual leaf to see only its ancestors recompute.

Pre-aggregation at every scale wins

Why pre-aggregation at every scale wins.

Why pre-aggregation at every scale wins.

Why pre-aggregation at every scale wins.

Think about how a calendar's month-view summary is built. Each cell shows a daily total. Each week shows a weekly total. The month shows a monthly total. When the user asks for “how much did I spend from the 7th to the 23rd?”, you don't add the daily numbers from the 7th to the 23rd. You take a few weekly totals plus a couple of daily values at the edges. The work is sub-linear in the size of the range because you've been keeping totals at multiple zoom levels.

A segment tree generalises this idea to power-of-two zoom levels and to any associative operation, not just sum. Level zero is the raw array. Level one pre-aggregates pairs. Level two pre-aggregates fours. Level three pre-aggregates eights. The very top is the whole-array aggregate. There are log₂ n levels, and each level holds about n values across all its nodes — so the total memory is O(n) and the height is O(log n). The trade is space: the segment tree uses about 2n array slots, double the original. For most workloads that's an excellent trade for O(log n) range operations.

The trade-off list has only one entry. Sum has the cheaper alternative of a prefix-sum array, with O(1) queries instead of O(log n) — but no support for updates and no support for non-invertible operations. Min and max can use a sparse table, an O(n log n) precomputation that answers immutable range-min/max queries in O(1) — but again no updates. The segment tree is the answer when both updates and arbitrary associative aggregates are required. The simulator's modes (sum, min, max, GCD) all run on the same tree shape; only the combine function differs.

Building a segment tree — leaves first, then walk up

Leaves first, then walk up.

The simulator uses the iterative variant: an array tree of size 2n, where positions [n, 2n) hold the leaves (a copy of the input array) and positions [1, n) hold internal nodes. Position 0 is unused — it makes the parent/child arithmetic clean.

function build(arr) {
  const n = arr.length;
  const tree = new Array(2 * n).fill(0);
  for (let i = 0; i < n; i++) tree[n + i] = arr[i];   // leaves
  for (let i = n - 1; i > 0; i--) {                    // internal, bottom-up
    tree[i] = combine(tree[2 * i], tree[2 * i + 1]);
  }
  return tree;
}

Each internal node aggregates exactly its two children, so the sweep does O(n) work — one combine per internal node, n − 1 of them. The root at index 1 holds the aggregate over the entire array. The recursive variant builds the same tree but allocates 4n slots to handle non-power-of-two sizes; both are correct, the iterative version is simpler and faster for power-of-two-friendly cases.

Range query — walk left and right pointers up the tree

Walk left and right pointers up the tree.

A range query [l, r] walks two pointers from the leaf level upward, picking off every node whose entire range fits inside [l, r] without overshoot. The classical iterative form:

function query(lo, hi) {
  const n = arr.length;
  let res = identity;
  let l = lo + n, r = hi + n + 1;        // [l, r) in tree space
  while (l < r) {
    if (l & 1) res = combine(res, tree[l++]);   // left edge: include
    if (r & 1) res = combine(res, tree[--r]);   // right edge: include
    l >>= 1; r >>= 1;                       // climb a level
  }
  return res;
}

At each level the algorithm asks: is the current left pointer a right-child? If yes, this position is not fully contained in any ancestor's range we'd visit, so include it now and move past. The mirror logic applies on the right. Then both pointers shift up one level. The walk does at most 2 includes per level × log₂ n levels = at most 2·log₂ n aggregate combines.

The covering set — the nodes whose values get folded into the answer — is highlighted in the simulator. Try query 1..5 on the default array. Notice how the algorithm picks four nodes, never six or eight: it's already-aggregated nodes at the best granularity, never duplicating work. This is exactly the property that makes the algorithm O(log n) instead of O(n).

Point update — only its ancestors care

A leaf changes — only its ancestors care.

When you update a single array position, only the leaf at that index changes — and only the ancestors of that leaf need their aggregates recomputed. That's a path of length log₂ n from leaf to root. Each step combines two children, so the total work is O(log n).

function pointUpdate(idx, val) {
  let i = idx + n;
  tree[i] = val;
  i >>= 1;
  while (i > 0) {
    tree[i] = combine(tree[2 * i], tree[2 * i + 1]);
    i >>= 1;
  }
}

The simulator's point update button does exactly this. After the change, the values along the path from the modified leaf to the root all flicker as they're recomputed. Every other internal node is unchanged.

A common interview-grade variant: range update with point query. If you need to add +5 to every element in [lo, hi] and later read individual elements, you can store a "delta" at each tree node and propagate it lazily on read. This is the dual of range query with point update (the simulator's default). The two are connected via a clever trick: the segment tree of differences. Both run in O(log n).

Lazy propagation — range update without touching every element

Add 5 to every element in a range — without touching all 45.

A naive range update would touch every leaf in the range — O(r − l) — and then update O(log(r − l)) ancestors per leaf. Total: O(n log n) for a single big-range update. Unacceptable.

Lazy propagation sidesteps this. When the algorithm encounters a node whose entire range is contained in the update range, it modifies that node's aggregate value (e.g. sum += 5 × node.size) and stores a "lazy" tag at the node — the operation that's been promised to its descendants but not yet applied. On any future query or update that needs to descend below this node, we first push down the lazy tag to the children, then continue.

function rangeUpdate(node, lo, hi, qlo, qhi, delta) {
  if (qhi < lo || hi < qlo) return;        // no overlap
  if (qlo <= lo && hi <= qhi) {            // total overlap
    tree[node] += delta * (hi - lo + 1);    // apply to aggregate
    lazy[node] += delta;                    // remember for descendants
    return;
  }
  pushDown(node, lo, hi);                   // propagate before descending
  const mid = (lo + hi) >> 1;
  rangeUpdate(node*2, lo, mid, qlo, qhi, delta);
  rangeUpdate(node*2+1, mid+1, hi, qlo, qhi, delta);
  tree[node] = tree[node*2] + tree[node*2+1];
}

With lazy propagation, both range queries and range updates run in O(log n) amortised. Every push-down does constant work, and the number of nodes a query/update path visits is bounded by O(log n).

Lazy tags can be combined or replaced depending on the operation. For "set every element in range to X," the lazy tag overwrites; for "add X," it accumulates. Some implementations support both kinds of updates by storing two tags per node, with a precedence rule (a "set" cancels any pending "add" on the same node).

Where segment trees ship — beyond competitive programming

Production roles, beyond competitive programming.

• Editor range minimum/maximum queries — vim and emacs use them indirectly to maintain things like "lowest indentation in selection" or "longest line in viewport" cheaply.
• Database query optimisers use range-aggregate structures over indexed columns when planning hash partitions.
• Time-series databases (InfluxDB, Prometheus internals) use segment-tree-like decompositions to answer "max latency in this minute" without scanning every sample.
• Computational geometry: 1-D segment trees underpin the standard sweep-line algorithms for "find all rectangles overlapping the query rectangle."
• Counting inversions, range-rank queries, finding the k-th smallest element in a range — competitive-programming staples that show up in real systems whenever you need to answer "how many records satisfy <condition> in this range" without a per-query scan.
• Game state diff in turn-based games — checking whether any unit's status changed in a region between turns.

The structure has many cousins. Fenwick trees (binary indexed trees) use less space (n slots, not 2n) and have simpler code, but only support invertible operations like sum and XOR — no min/max. Sparse tables precompute O(n log n) values and answer immutable range-min/max queries in O(1), but don't support updates. Wavelet trees generalise to range-rank queries on arbitrary alphabets. Persistent segment trees keep every historical version with O(log n) extra space per update — useful when you need "what was the answer 100 updates ago?"

Fenwick (BIT) trees — half the code, but only for invertible aggregates

Half the code, half the memory — but only for invertible aggregates.

For the specific case of prefix-sum range queries with point updates, the segment tree's poorer cousin — the Fenwick tree or binary indexed tree (BIT) — is faster, smaller, and shorter to write. It uses a single array of n integers (no 2n) and the entire structure fits in 12 lines.

const bit = new Array(n + 1).fill(0);

function update(i, delta) {
  for (i++; i <= n; i += i & -i) bit[i] += delta;
}

function prefixSum(i) {
  let s = 0;
  for (i++; i > 0; i -= i & -i) s += bit[i];
  return s;
}

function rangeSum(l, r) {
  return prefixSum(r) - prefixSum(l - 1);
}

The trick is the bit-twiddle i &= -i, which extracts the lowest set bit of i — and which conveniently encodes which "responsibility region" each array slot covers. Slot 4 covers indices 1..4. Slot 6 covers indices 5..6. Slot 12 covers indices 9..12. Update walks up the implicit tree adding the delta; query walks down, summing the contributing regions. Both are O(log n) with extremely tight constants — typically 2-3× faster than an iterative segment tree on the same workload.

The catch: Fenwick trees only work for invertible aggregates. The range-sum identity sum(l..r) = prefix(r) − prefix(l − 1) requires subtraction. Min and max are not invertible — there's no "subtract a min" operation. If your aggregate is sum, count, or XOR, prefer a Fenwick tree. If it's min, max, GCD, or any non-invertible operation, you need a segment tree.

Two-dimensional Fenwick trees and Fenwick trees with range updates exist (the "BIT of BIT" trick), but past the basic 1D point-update prefix-sum case, segment trees become competitive again because their flexibility starts paying off.

Where segment trees earn their reputation

Where the structure earns its rare-air reputation.

A regular segment tree handles 1D ranges. The structure generalises in three meaningful directions, each used in production.

2D segment trees: each node of the outer tree (over rows) is itself a segment tree (over columns). Total memory is O(n²), query is O(log² n). Used for "what's the sum of values in rectangle [r1..r2] × [c1..c2]?" — image processing, computational geometry, GIS spatial queries. The brute-force alternative is a 2D prefix-sum array which gives O(1) query but doesn't allow updates. Segment trees of segment trees are the right choice when the matrix changes between queries.

Persistent segment trees: every update returns a new tree sharing most nodes with the old one. Memory cost per update is O(log n) — exactly the path of changed nodes. Useful when you want "what was the value of arr[i] after the kth update?" or "what's the answer to a query against the version of the tree before update t?" Time-travel debugging, version control internals, and certain offline algorithms (Mo's algorithm with rollback) all use persistent segment trees.

Merge-sort trees: each node stores its leaf range in sorted order. Total memory: O(n log n). Useful for "how many elements in [l..r] are less than k?" — a 2D dominance query that no other simple structure handles efficiently. Build is O(n log n), query is O(log² n) using binary search at each visited node.

All three variants share the same conceptual core: pre-aggregate at every power-of-two granularity, then answer queries by combining a logarithmic number of pre-aggregated pieces. Once that mental model clicks, dozens of variant problems become applications of the same idea.

The structure also extends to convex hull tricks (upper-envelope segment trees for dynamic linear-function arithmetic), Li Chao trees (1D segment tree where each node stores a function instead of a value), and wavelet trees (segment tree over the alphabet of a string instead of an array index). Each adds expressive power; each pays in implementation effort and constant factor. The default segment tree from this simulator is the trunk; the variants are branches you reach for when a profile demands them.

There is a final, mostly-academic relative worth knowing: the iterative segment tree on arbitrary intervals (sometimes called a "non-recursive segment tree with lazy propagation"). The idea is to drop the implicit assumption that the leaf range is [0, n) and let the tree index any interval system, even non-contiguous ones. Implementations are tricky because the index arithmetic stops being clean, but the structure becomes useful when the underlying domain is sparse — for instance, "events at known timestamps" rather than "values at indices 0..n − 1." Most production code skips this generalisation and discretises the domain to dense indices; the niche cases that benefit are rare enough that you'll know when you need them.

Implementing segment trees three different ways

Implement them three different ways.

Segment trees become muscle memory only after you've written them at least three times. The progression:

1. Iterative bottom-up (the simulator's variant). Easiest to reason about for power-of-two sizes. Build / query / point-update fit in 30 lines total.
2. Recursive top-down. Allocate 4n nodes; query and update take a (node, lo, hi) triple; descend with overlap checks. The natural form for lazy propagation.
3. Persistent / immutable. Each update returns a new tree sharing most nodes with the old one. Useful for "undo" or "snapshot" workloads. Adds O(log n) memory per update.

After those three, problems to chew on:

4. Range sum + point update. Implement, then time it against a Fenwick tree on 1M operations. The Fenwick is faster (smaller constant); use this to internalise when the segment tree is the wrong tool.
5. Range minimum query. Implement, then implement a sparse table for the same workload (no updates). Compare query latency.
6. Range update, point query. The dual problem — flip the roles by using a difference array.
7. Range update, range query, with lazy. The full beast. Most tutorials only get you to here.
8. Range count of distinct elements. Needs offline processing with Mo's algorithm or a more elaborate data structure (BIT of BITs / persistent segment tree).
9. 2D range sum. Build a segment tree of segment trees. Query is O(log² n). The interview-killer.

Where segment trees silently go wrong

Where it silently goes wrong.

Off-by-one in interval semantics. Decide once and stick with it: are intervals [lo, hi] closed-closed, [lo, hi) closed-open, or 1-indexed? Mixing conventions across functions is the #1 cause of off-by-one bugs in segment-tree code.

Identity element for min/max. Use +Infinity for min and -Infinity for max; for integer types use INT_MAX / INT_MIN. If you use 0 as the identity for min on an array of positive numbers, queries on empty ranges return zero — usually wrong.

Lazy propagation order matters. Always push the parent's lazy tag down to children before descending. If you forget, the children's aggregates are stale and queries return wrong answers.

Memory. The recursive 4n variant is safe for any n. The iterative 2n variant assumes power-of-two — for arbitrary n you can pad to the next power of two with identity values, or use the recursive form.

Operations must be associative. Sum, min, max, GCD, XOR, matrix multiplication all qualify. Subtraction does not. Division does not. If your operation isn't associative, a segment tree won't help.

Further reading on segment trees

Primary sources, in order.

• Bentley · 1977
  Solutions to Klee's Rectangle Problems
  Carnegie-Mellon technical report. The earliest formal description of the segment tree as we now teach it, motivated by computational geometry sweep-line algorithms.
• Codeforces EDU
  Segment Tree, Part 1 & 2
  The most rigorous free interactive course on the topic. Pavel Mavrin's exposition starts from O(n) build and ends with persistent + 2D variants.
• al.cash · Codeforces
  Efficient and easy segment trees
  The iterative variant in 30 readable lines. The version most competitive programmers reach for first.
• CP-Algorithms
  Segment Tree — encyclopedic reference
  Covers every variant: lazy propagation, persistent, 2D, merge-sort tree, segment tree on the segments themselves. Free, open-source, frequently updated.
• CLRS · 4th ed., 2022
  Introduction to Algorithms — Augmenting Data Structures (Ch. 17)
  The textbook chapter on building range structures from balanced BSTs. Pairs well with the segment tree as the array-indexed dual.
• Fenwick · 1994
  A New Data Structure for Cumulative Frequency Tables
  Software Practice & Experience. The original Fenwick tree paper — the n-word, 12-line cousin of the segment tree.
• Frigo, Leiserson, Prokop, Ramachandran · 1999
  Cache-Oblivious Algorithms
  FOCS 1999. Why segment-tree memory layouts (van Emde Boas, Eytzinger) matter at large scale; the bridge between asymptotic and wall-clock time.
• Sedgewick · Coursera
  Algorithms, Part I — Princeton
  Robert Sedgewick's free MOOC. Range-tree material in week 4. Excellent companion lectures with Java code on the book site.
• MIT 6.851 · OCW
  Advanced Data Structures — Erik Demaine
  Lectures on persistent and retroactive data structures. The graduate-level treatment of why “snapshot every version” is cheaper than it sounds.
• Semicolony simulator
  B-tree
  A different range-query approach: ordered scalar keys with disk-resident pages and range scans.
• Semicolony simulator
  Heap
  The priority-queue cousin: also a balanced binary tree, also O(log n) per operation, but answering “the min” rather than “the min of a range.”