Segment Tree: Range Queries in O(log n)

The trade a plain array can't make

Given an array, two operations pull in opposite directions. Answering "what is the sum (or min) of elements i..j" is O(1) if you precompute prefix sums, but then updating a single element costs O(n) because every prefix after it is now wrong. Doing nothing in advance makes an update O(1) but a query O(n). A segment tree refuses that trade: both operations cost O(log n), by storing not just the array but the aggregate of every range that a balanced recursive split can produce.

live demo · a tree of ranges being queried and updated● LIVE

Building the tree

The root covers the whole array [0, n). Every internal node splits its range in half and hands the halves to its two children; a leaf covers a single element. Because the tree always splits evenly, it has height ⌈log₂ n⌉ and about 2n − 1 nodes, commonly stored in an array of size 4n for a simple index scheme without pointers:

function build(node, lo, hi) {
  if (lo === hi) { tree[node] = a[lo]; return; }
  const mid = (lo + hi) >> 1;
  build(2*node, lo, mid);
  build(2*node+1, mid+1, hi);
  tree[node] = combine(tree[2*node], tree[2*node+1]);  // sum, min, gcd...
}

Building visits every node once, so construction is O(n) even though the tree looks recursively expensive on paper.

Answering a range query

Any query range [l, r] can be exactly covered by a small set of node ranges already stored in the tree — its canonical decomposition. The query recursion stops the instant a node's range falls entirely inside or entirely outside [l, r], and only descends further when the ranges partially overlap:

function query(node, lo, hi, l, r) {
  if (r < lo || hi < l) return IDENTITY;       // no overlap
  if (l <= lo && hi <= r) return tree[node];    // fully covered
  const mid = (lo + hi) >> 1;
  return combine(query(2*node, lo, mid, l, r),
                 query(2*node+1, mid+1, hi, l, r));
}

At each depth of the tree, at most two nodes can be partially overlapping the query — one containing the left boundary, one containing the right — so the whole query touches only O(log n) nodes total, no matter how wide the range is.

Point update, and lazy propagation for range updates

Updating a single element walks the same root-to-leaf path used to build the tree, changes the leaf, then recombines every ancestor on the way back up — O(log n) nodes touched, matching the query cost exactly. Updating a whole range at once (add 5 to every element from i to j) is where a naive point-by-point update becomes O(n log n) and a smarter trick is needed: lazy propagation. A node whose range is fully covered by the update stores a pending tag instead of updating every descendant immediately; the tag is only pushed down to the children the next time the query or update recursion actually needs to look inside that node.

function pushDown(node, lo, hi) {
  if (!lazy[node]) return;
  const mid = (lo + hi) >> 1;
  applyTag(2*node, lo, mid, lazy[node]);
  applyTag(2*node+1, mid+1, hi, lazy[node]);
  lazy[node] = 0;
}

With lazy tags, both range updates and range queries stay O(log n), which is what makes segment trees the standard tool for problems that mix "add x to everything in [l, r]" with "what's the sum/min of [l, r]" in the same workload.

Segment tree, Fenwick tree, or sparse table?

A Fenwick tree (binary indexed tree) does the same O(log n) prefix-sum query and point update with far less code and a smaller constant factor, but it only works cleanly for invertible operations like sum, where you can subtract to get an arbitrary range from two prefixes — it cannot support min or max directly. A sparse table answers range-min or range-gcd queries in O(1) after an O(n log n) build by precomputing every power-of-two-length range, but it is static: it exploits idempotence (overlapping the same element twice doesn't break a min or gcd) and has no efficient way to handle updates at all. The segment tree is the generalist: any associative combine function, with updates, in O(log n) on both sides — the price for that generality is exactly the extra tree structure the other two skip.

Frequently asked questions

Why not just precompute prefix sums instead of building a segment tree?

Prefix sums answer a range-sum query in O(1), which is faster than a segment tree's O(log n) — but updating one element then costs O(n), because every prefix sum after it changes. A segment tree accepts a slightly slower query in exchange for an update that is also O(log n), which is the right trade whenever the array changes.

Why does a query only ever touch O(log n) nodes?

Because the recursive query only recurses into a child when the query range partially overlaps it, and stops immediately when a node's range is fully inside or fully outside the query. At each depth of the tree at most two nodes can be partially overlapping (one on the left boundary, one on the right), so the total number of visited nodes is bounded by a small constant times the tree height, O(log n).

When should I use a Fenwick tree (BIT) instead of a segment tree?

Use a Fenwick tree when the operation is invertible, like a sum, and you only need prefix queries — it does the same O(log n) update and query with less code and a smaller constant factor. Reach for a segment tree when the operation is non-invertible (min, max, gcd), when you need lazy range updates, or when you need arbitrary range queries beyond prefixes.

Try it live

Everything above runs in your browser — open Segment Tree and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.

▶ Open Segment Tree simulation