Segment Tree

How a segment tree works

Imagine an array of length n. A segment tree is a complete binary tree built over that array: every leaf corresponds to one element, and every internal node holds the aggregate (sum, min, max — whatever you're tracking) of the range covered by its leaves. Node 1 is the root and covers [0, n-1]; its left child covers the first half and its right child covers the second.

The structure has two superpowers:

• Range query in O(log n). To compute the aggregate of [l, r], the query recurses from the root and stops at every node whose range is entirely inside [l, r]. The number of such "stop nodes" is at most 4·log₂(n) — the recursion descends each side of the query interval and prunes once it falls fully inside.
• Update in O(log n). Touching a single element only affects O(log n) ancestors. Walk up from the leaf, recomputing aggregates with the merge function, and stop at the root.

Storage is the catch. A segment tree over n leaves needs at most 4n cells when allocated as a flat array using the "node 1 is the root, 2i and 2i+1 are its children" indexing. Memory layout matters: a flat Int32Array(4n) is cache-friendly and beats explicit-node implementations by a wide margin in tight loops.

Lazy propagation in one paragraph

Range updates without lazy propagation cost O(n) — you'd have to touch every leaf in the range. Lazy propagation adds a second array, lazy[], parallel to the tree. When a range update fully covers a node's range, you (1) update that node's aggregate to reflect the change applied to all of its leaves and (2) record the change in lazy[node] instead of recursing further. Later, when a query or update visits that node's children, you "push down": apply the pending change to both children, propagate it into their lazy tags, and clear the parent's lazy. Total work per range update is the same O(log n) as a point update.

The bookkeeping is fiddly because the merge function for the lazy tag is operation-specific: range-add lazy tags compose by addition, range-assign lazy tags compose by overwrite (newer wins), range-multiply by multiplication. Mixing two update kinds (e.g. add + assign) requires storing both tags and applying them in defined order.

When to use a segment tree

• Range min/max/gcd/lcm queries — operations without inverses, ruling out a Fenwick tree.
• Range updates with non-trivial semantics: range-assign, range-flip, range-add-and-multiply.
• Aggregate types that don't compress into a single number: pair (min, second-min), histogram, top-k.
• Persistent versions for time-travel queries (k-th smallest, count distinct in [l, r]).
• Any time you can describe the answer as a fold over a range — segment trees handle the most general "monoid range fold" pattern.

Skip the segment tree when you only need prefix sums and point updates — a Fenwick tree is simpler and faster. Skip it for problems where queries are offline and can be sorted: Mo's algorithm with a sqrt-decomposition is often easier and competitive.

Segment tree vs Fenwick tree vs sqrt-decomposition

	Segment tree	Fenwick tree	Sqrt-decomposition
Range query	O(log n), any monoid	O(log n), only invertible	O(√n)
Point update	O(log n)	O(log n)	O(1)
Range update	O(log n) with lazy	O(log n) for sum only (BIT2)	O(√n)
Memory	≈4n	n+1	n + √n
Code length	40-80 lines	~12 lines	~25 lines
Operations supported	Any monoid (assoc.)	Group only (sum, XOR)	Any monoid
Persistence	Easy (path-copy)	Hard	Block snapshots
Constant factor	2-3× Fenwick	Smallest	Cache-friendly, ~Fenwick
Best for	min/max/range-update	sum + point-update	weird ops, Mo's algo

If you remember one rule: Fenwick if you can, segment tree if you must, sqrt-decomposition for the weird stuff like distinct counts or mode in a range.

Pseudo-code (range-min, point-update)

tree = array of size 4n

function build(node, l, r):
    if l == r:
        tree[node] = arr[l]
        return
    mid = (l + r) / 2
    build(2*node,   l,     mid)
    build(2*node+1, mid+1, r)
    tree[node] = min(tree[2*node], tree[2*node+1])

function query(node, l, r, ql, qr):
    if qr < l or r < ql: return INF
    if ql <= l and r <= qr: return tree[node]
    mid = (l + r) / 2
    return min(query(2*node,   l,     mid, ql, qr),
               query(2*node+1, mid+1, r,   ql, qr))

function update(node, l, r, idx, value):
    if l == r:
        tree[node] = value
        return
    mid = (l + r) / 2
    if idx <= mid: update(2*node,   l,     mid, idx, value)
    else:          update(2*node+1, mid+1, r,   idx, value)
    tree[node] = min(tree[2*node], tree[2*node+1])

JavaScript implementation — range min

class SegTreeMin {
  constructor(values) {
    this.n = values.length;
    this.tree = new Int32Array(4 * this.n).fill(Number.MAX_SAFE_INTEGER);
    this.build(1, 0, this.n - 1, values);
  }
  build(node, l, r, a) {
    if (l === r) { this.tree[node] = a[l]; return; }
    const mid = (l + r) >> 1;
    this.build(2 * node,     l,       mid, a);
    this.build(2 * node + 1, mid + 1, r,   a);
    this.tree[node] = Math.min(this.tree[2 * node], this.tree[2 * node + 1]);
  }
  query(ql, qr, node = 1, l = 0, r = this.n - 1) {
    if (qr < l || r < ql) return Number.MAX_SAFE_INTEGER;
    if (ql <= l && r <= qr) return this.tree[node];
    const mid = (l + r) >> 1;
    return Math.min(
      this.query(ql, qr, 2 * node,     l,       mid),
      this.query(ql, qr, 2 * node + 1, mid + 1, r)
    );
  }
  update(idx, value, node = 1, l = 0, r = this.n - 1) {
    if (l === r) { this.tree[node] = value; return; }
    const mid = (l + r) >> 1;
    if (idx <= mid) this.update(idx, value, 2 * node,     l,       mid);
    else            this.update(idx, value, 2 * node + 1, mid + 1, r);
    this.tree[node] = Math.min(this.tree[2 * node], this.tree[2 * node + 1]);
  }
}

For 10^6 nodes, this implementation handles roughly 20 million queries per second in V8. The recursive form is the easiest to understand; an iterative bottom-up version (Atcoder library style) gets to ~50M/s by killing function call overhead.

Python implementation — range sum with lazy add

Range-add, range-sum is the canonical "introduce yourself to lazy propagation" exercise. The lazy tag stores a pending "add this much to every leaf below me", and pushes down on every visit.

class SegTreeRangeSum:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (4 * n)
        self.lazy = [0] * (4 * n)

    def _push(self, node, l, r):
        if self.lazy[node]:
            mid = (l + r) // 2
            for child, cl, cr in ((2*node, l, mid), (2*node+1, mid+1, r)):
                self.tree[child] += self.lazy[node] * (cr - cl + 1)
                self.lazy[child] += self.lazy[node]
            self.lazy[node] = 0

    def update(self, ql, qr, val, node=1, l=0, r=None):
        if r is None: r = self.n - 1
        if qr < l or r < ql:
            return
        if ql <= l and r <= qr:
            self.tree[node] += val * (r - l + 1)
            self.lazy[node] += val
            return
        self._push(node, l, r)
        mid = (l + r) // 2
        self.update(ql, qr, val, 2*node,   l,     mid)
        self.update(ql, qr, val, 2*node+1, mid+1, r)
        self.tree[node] = self.tree[2*node] + self.tree[2*node+1]

    def query(self, ql, qr, node=1, l=0, r=None):
        if r is None: r = self.n - 1
        if qr < l or r < ql:
            return 0
        if ql <= l and r <= qr:
            return self.tree[node]
        self._push(node, l, r)
        mid = (l + r) // 2
        return (self.query(ql, qr, 2*node,   l,     mid)
              + self.query(ql, qr, 2*node+1, mid+1, r))

This solves the standard "n elements, m operations of add(l, r, val) and sum(l, r)" problem in O((n + m) log n). For competitive constraints n, m ≤ 10^5 it's fast enough in Python; for 10^6 you typically port to C++ or rewrite as iterative segment tree.

Variants

Iterative segment tree (Atcoder style)

For point updates and range queries (no lazy), there's a beautiful iterative version: store the tree in tree[1..2n], leaves at tree[n..2n-1]. Update walks up from leaf n + i; query starts at the leaf range and accumulates while walking up, taking the left child if the index is odd and the right child if even. ~30 lines, no recursion, ~2× faster.

Lazy propagation with multiple tags

Many problems require both range-assign and range-add. Define a composition rule: assign overwrites add (apply assign first, then add). Each node stores both a pending assign value and a pending add value, and pushdown applies them in order. Easy to get wrong — write a 5-line monoid abstraction once and reuse.

Persistent segment tree

Each update returns a new root, sharing all nodes that didn't change. After q updates total memory is O(n + q log n), and you can query any historical version. Used for "k-th smallest in [l, r]" by building a persistent BIT-like structure where version i is the histogram of arr[0..i]; the answer is a walk over version r minus version l-1.

Segment tree beats

Chtholly tree / Ji Driver Segment Tree handles operations like "set every value in [l, r] to min(value, x)" in amortised O(log² n). The trick: each node stores max and second-max; if x ≥ max, no change; if max > x ≥ secondMax, update only the max contribution; else recurse. Surprising but real.

2D segment trees

Tree of trees: outer tree on rows, each node stores a segment tree on columns. Submatrix sum and point update both O(log² n). Memory blows to O(n² log n) without compression — use only when truly necessary.

Common bugs and edge cases

• Allocating too little memory. Always allocate 4n, even if you "know" that 2 · 2^⌈log₂ n⌉ is enough — the off-by-one bites you on n that's not a power of two.
• Forgetting to pushdown before recursing. Skipping pushdown causes children to see a stale aggregate; queries return wrong answers silently.
• Pushing down on a leaf. Leaves have no children. Guard with if l != r.
• Using a wrong identity for range queries that miss entirely. Min queries return INF, max queries return -INF, sum queries return 0, product queries return 1. Pick the identity that op(x, identity) = x.
• Writing (l + r) / 2 in C++ with signed int. If l + r overflows, behaviour is undefined. Use l + (r - l) / 2 or unsigned.
• Lazy tag for non-commutative updates. If updates don't commute (e.g., assign-then-add behaves differently than add-then-assign), you must store the tag and a small DFA describing operation order, not just two numbers.
• Hidden recursion blow-up in JavaScript. Default V8 stack handles ~10k frames; a recursive segment tree on 10^6 elements descends ~20 levels per call, so it's safe — but if you write this.query(...) with arrow functions and lots of closures, GC pressure becomes the bottleneck. Profile before optimising.