Segment Trees: The Mental Model

Fenwick covers sum and XOR. The next problems ask for range minimum, range gcd, or 'first index in [l,r] whose value is ≥ x'. Those combines are not invertible, so two prefixes do not help.

A segment tree stores a value at every node of a binary tree whose leaves are the array. The node for [L,R) holds combine(left, right). A query [l,r) is the combine of O(log n) canonical nodes that tile the query. A point update touches the leaf and its O(log n) ancestors.

CSES Dynamic Range Minimum Queries is the drill. This lesson does not ship a visual editor — you need the recurrence and the walk, not a GUI.

Iterative segment tree, size rounded up to a power of twojs

function createSegMin(a) {
  let n = 1;
  while (n < a.length) n <<= 1;
  const t = Array(2 * n).fill(Infinity);
  for (let i = 0; i < a.length; i++) t[n + i] = a[i];
  for (let i = n - 1; i > 0; i--) t[i] = Math.min(t[i << 1], t[(i << 1) | 1]);
  function set(i, v) {
    i += n;
    t[i] = v;
    for (i >>= 1; i; i >>= 1) t[i] = Math.min(t[i << 1], t[(i << 1) | 1]);
  }
  function rangeMin(l, r) {
    // half-open [l, r)
    let ans = Infinity;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) ans = Math.min(ans, t[l++]);
      if (r & 1) ans = Math.min(ans, t[--r]);
    }
    return ans;
  }
  return { set, rangeMin };
}

TRACE

n = 4, tree leaves [2, 5, 1, 4] at indices 4..7. Query min[1, 3) = min(5, 1).

Build

Leaves t[4]=2, t[5]=5, t[6]=1, t[7]=4. t[2]=min(2,5)=2, t[3]=min(1,4)=1, t[1]=min(2,1)=1.

t[1]=1 is the whole array

1 / 3

CHECK

When do you pick a Fenwick over a segment tree?

CHECK

Identity for range min on an empty combine (the ans starter) is…

CSES twins: Static Range Minimum (can be sparse table — O(1) query, no updates), Dynamic Range Minimum (this tree), Range Update Queries (lazy or Fenwick difference). You do not need to type a recursive build in contest if you have the iterative template above; you do need to know what [l,r) means so you do not drop the last index.

Checks 0/2

Next lesson