↩ back to Array-Backed Trees

Segment Tree (Range Minimum Query)

A Fenwick tree gets point-update and prefix-sum both down to O(log n), but only for operations with an inverse — sum works because subtraction undoes addition, so rangeSum(l, r) = query(r) - query(l-1). Range minimum has no such trick: knowing the smallest value up to index r and the smallest value up to index l-1 tells you nothing about whether the true minimum of [l, r] came from the earlier or later part. A segment tree asks for less — not an inverse, just an associative combining rule — and in exchange supports arbitrary range queries: min, max, sum, gcd, and more, all in O(log n), all with the same structure.

Try it

The array below has 8 values, indexed 0 through 7. Below it is the segment tree itself: node 1 (the root) covers the whole array, and every node's two children split its range in half, down to the 8 leaves — each holding one value, each internal node holding the minimum of everything beneath it. Pick an index and a new value and press Set to update, or pick a range and press Query Min, then step through to see exactly which nodes get touched and why.

Why it works

Every node i owns a fixed range of the array, split evenly between its two children (node 2i and node 2i+1), all the way down to the 8 leaves (nodes 8-15) which each own exactly one index. On the default array [5, 2, 8, 1, 9, 3, 7, 4]: node 1 covers [0,7], its children node 2 and node 3 cover [0,3] and [4,7], and so on down to node 11 ([3,3], value 1) and node 14 ([6,6], value 7). Each internal node just stores min(leftChild, rightChild), so the root always holds the minimum of the whole array with no work beyond what its two children already know.

Querying a range means finding the fewest nodes whose ranges tile it exactly, with no overlap and nothing extra. Query min over [1, 5] on the default tree touches exactly three nodes: node 9 ([1,1], value 2), node 5 ([2,3], value 1), and node 6 ([4,5], value 3) — three ranges that concatenate to precisely [1,5], no more, no less. The answer is min(2, 1, 3) = 1. The mechanism that finds exactly those three nodes without ever visiting an irrelevant one is two pointers walking up from the query's endpoints in lockstep (lo from the left, hi from the right), picking up a node's value whenever a pointer lands on an odd (right-hand-child) index before climbing a level — the same "at most log₂(n) steps" argument as Fenwick's bit-stripping walk, just shaped around tree levels instead of set bits.

Updating a value only ever needs to fix the O(log n) nodes on the direct path from that leaf to the root — every other node's range doesn't contain the changed index, so its minimum can't have changed. Setting index 3 from 1 to 6 changes leaf node 11 directly, then its parent node 5 (min(8, 6) = 6, was 1), then node 2 (min(2, 6) = 2, unchanged since index 1's value 2 was already smaller), then the root node 1 (min(2, 3) = 2, was 1) — the array's old minimum was sitting at the index that just changed, so the root's answer genuinely changes too, not just the nodes on the way there.

Reference implementation

This is the iterative, bottom-up form of a segment tree: a single flat array of size 2 · size (leaves start at index size), where size is the next power of two at or above the input length. Extra leaves beyond the real data are padded with Infinity — the identity value for min, so a padded leaf can never win a query and never needs special-casing:

class SegmentTreeMin {
  constructor(values) {
    let size = 1;
    while (size < values.length) size *= 2;
    this.n = size;
    this.tree = new Array(2 * size).fill(Infinity);
    for (let i = 0; i < values.length; i++) this.tree[size + i] = values[i];
    for (let i = size - 1; i >= 1; i--) {
      this.tree[i] = Math.min(this.tree[2 * i], this.tree[2 * i + 1]);
    }
  }

  update(i, value) {
    let pos = i + this.n;
    this.tree[pos] = value;
    for (pos >>= 1; pos >= 1; pos >>= 1) {
      this.tree[pos] = Math.min(this.tree[2 * pos], this.tree[2 * pos + 1]);
    }
  }

  queryMin(l, r) {                 // inclusive range [l, r]
    let res = Infinity;
    let lo = l + this.n, hi = r + 1 + this.n;
    while (lo < hi) {
      if (lo & 1) res = Math.min(res, this.tree[lo++]);
      if (hi & 1) res = Math.min(res, this.tree[--hi]);
      lo >>= 1; hi >>= 1;
    }
    return res;
  }
}

Pitfalls

Associative, not invertible — that's the whole trade against Fenwick. A segment tree works for any operation where combine(combine(a, b), c) == combine(a, combine(b, c)) — min, max, sum, gcd, bitwise AND/OR all qualify. It does not need an inverse the way Fenwick's sum-based prefix trick does, which is exactly why it can do min/max and Fenwick structurally can't. That generality isn't free: for a genuinely invertible operation like sum, a Fenwick tree is simpler code and about half the memory (one array of size n+1 instead of up to 4n) — reach for a segment tree specifically when the operation you need has no inverse, not as a default upgrade.

This iterative layout needs a power-of-two size, or padding. Doubling from leaf to root only lines up cleanly with size leaves where size is a power of two — the reference implementation above pads any shorter input up to the next one, filling the extra leaves with Infinity so they never win a min query. Padding with the wrong identity value (say, 0 instead of Infinity) would silently corrupt every real query that happens to include a padded leaf — a genuinely easy mistake to make when switching the combining operation, since 0 is sum's identity but not min's. The more commonly taught recursive, top-down segment tree (explicit node ranges, usually a 4n-sized array or real node objects) avoids the power-of-two requirement entirely, at the cost of being a bit more code and, in most implementations, a bit slower in practice than this array's tight iterative loops.

Complexity

Time: O(log n) for both update and queryMin — an update walks one root-to-leaf path, a query visits at most two nodes per tree level. Building from an existing array is O(n), one backward pass computing each internal node from its two already-filled children, the same single-pass build style as the Fenwick tree's constructor. Space: O(n), but with a real constant-factor cost the Fenwick tree doesn't have — the tree array is 2 · size long, where size is padded up to a power of two, so it can run to nearly 4n in the worst case (an input just past a power-of-two boundary) versus Fenwick's tight n+1. Every update above touches exactly one array index — for updating a whole range at once without paying for every touched index individually, see Segment Tree with Lazy Propagation. If the array never changes at all, updates aren't worth paying for even at O(log n) — see Sparse Table for the same range-minimum query answered in O(1) once updates are off the table.

This site's guide, Choosing a Range Query Structure, compares this entry against the other five Array-Backed Trees structures that answer the same kind of question side by side.