TreesData structureaka range tree, statistic tree

Segment Tree

A binary tree over array intervals that answers range queries (sum, min, max, gcd) and point or range updates in O(log n).

▶ VisualizePattern: Prefix SumPractice (3)
Progress

Definition

A segment tree stores an array a[0..n-1] as a binary tree where each node covers a contiguous interval and holds an aggregate (sum, min, max, gcd, …) of that interval. The root covers [0, n-1], its children cover the two halves, and leaves cover single elements. Any query interval [l, r] decomposes into at most 2 log₂ n node intervals, so a range query is O(log n), and a point update only touches the O(log n) ancestors of one leaf.

The aggregate can be any associative operation with an identity (a monoid): + with 0, min with +∞, max with -∞, gcd with 0, matrix product, or custom structs like "maximum subarray sum". With lazy propagation the tree also supports range updates (add v to every element in [l, r]) in O(log n) by deferring work to nodes until they are visited.

Compared to a Fenwick Tree, a segment tree is more general (any monoid, range updates, "first index where prefix ≥ x" descents) at the cost of 2–4× memory and more code. Compared to a Sparse Table, it supports updates.

range querypoint updatelazy propagationO(log n)associative

Intuition

A mental model before the formal terms.

Think of a tournament bracket over the array where each match records the "winner" (max) or the "combined score" (sum) of the two teams below. To find the max over a range, you do not look at every element — you look at the few bracket nodes whose spans tile exactly your range. Updating one element re-plays only the matches on its path to the final, about log n of them.

A range [l, r] in an array of 16 elements can always be covered by at most 8 bracket nodes, and usually far fewer; that is the whole trick.

How it works

  1. Build: node i covers [lo, hi]; if lo == hi store a[lo]; otherwise build children on [lo, mid] and [mid+1, hi] and combine. With 1-based indexing children of i are 2i and 2i+1; allocate 4n slots.
  2. Query(l, r) at node covering [lo, hi]: if [lo, hi] is disjoint from [l, r] return the identity; if fully inside return the node value; otherwise combine the results of both children.
  3. Point update(idx, v): descend to the leaf for idx, set it, and recompute each ancestor on the way back up.
  4. Range update with lazy propagation: when an update fully covers a node, apply it to the node's aggregate and record the pending change in lazy[i]; before descending into a node, push its pending change to its children. Queries push down the same way.
  5. An iterative bottom-up version (size padded to a power of two, leaves at n..2n-1) is shorter and faster for point-update/range-query.

Why it works

Any interval [l, r] is split by the recursion into maximal aligned nodes: at each depth at most two nodes are partially covered (the ones containing l and r), so at most 2 nodes per level are visited and at most 4 log n nodes total.

Associativity guarantees that combining aggregates of adjacent pieces in tree order equals the aggregate over the whole range, regardless of how the range is split.

Lazy propagation is correct because a pending tag on a node exactly represents the effect not yet applied to its subtree; pushing it before any descent keeps every visited node accurate.

Operations

OperationDescriptionCost
build(a)Construct the tree bottom-up from the array.O(n)
query(l, r)Combine O(log n) covering nodes.O(log n)
update(i, v)Set a leaf and recompute its ancestors.O(log n)
rangeUpdate(l, r, v)Apply to covering nodes, deferring to children via lazy tags.O(log n)
descend / find firstWalk down to the first index where a prefix aggregate crosses a threshold.O(log n)

Recognition

How to tell a problem wants this.

  • An array with q interleaved range queries and updates, n, q ≤ 2·10^5 — O(nq) is too slow.
  • Query words: sum/min/max/gcd/count "in the range [l, r]", or "after updating index i".
  • Range assignment or range increment together with range query — lazy propagation.
  • Counting inversions, "number of elements less than x so far", or offline sweeps over coordinates.
“sum of subarray” → Prefix Sum“merge k sorted” → Divide and Conquer“range query” → Segment / Fenwick Tree

Interactive demo

Play, step, change the input. ← → and space work too.

Empty tree
Array a
531014628
1/65Build a sum segment tree over 8 elements. Each node stores the sum of a range; a leaf covers one index and the root covers [0,7].
Visiting (partial overlap / recursing)Fully covered — take its sumNo overlap — prunedRecomputed after update
PseudocodeLearn Segment Tree →
1build(node, l, r): if l == r: tree[node] = a[l]
2  else: build children over [l,mid], [mid+1,r]; tree[node] = left + right
3query(node, l, r, ql, qr):
4  if qr < l or r < ql: return 0            # no overlap
5  if ql <= l and r <= qr: return tree[node] # total overlap
6  return query(left) + query(right)         # partial overlap: split
7update(node, l, r, i, v): descend to leaf i, set it, recompute sums on the way up
Variables
n8
Complexity
access O(log n)
search O(n)
insert —
delete —
Speed

Pseudocode

1build(node, lo, hi):
2  if lo == hi: tree[node] = a[lo]; return
3  mid = (lo + hi) / 2
4  build(2node, lo, mid); build(2node+1, mid+1, hi)
5  tree[node] = combine(tree[2node], tree[2node+1])
6query(node, lo, hi, l, r):
7  if r < lo or hi < l: return IDENTITY
8  if l <= lo and hi <= r: return tree[node]
9  return combine(query(left half), query(right half))
10update(node, lo, hi, idx, v):
11  if lo == hi: tree[node] = v; return
12  recurse into the half containing idx; tree[node] = combine(children)

Implementation

11 · Storage: 4n tree array, combine and identity
2class SegmentTree:
3    """Range-sum segment tree with point update. Swap combine/identity for min, max, gcd."""
4 
5    identity = 0
6 
7    def __init__(self, a: list[int]):
8        self.n = len(a)
9        self.tree = [0] * (4 * self.n if self.n else 4)
10        if self.n:
11            self._build(a, 1, 0, self.n - 1)
12 
13    @staticmethod
14    def combine(x: int, y: int) -> int:
15        return x + y
16 
172 · Build: leaves store a[i], parents combine children
18    def _build(self, a: list[int], node: int, lo: int, hi: int) -> None:
19        if lo == hi:
20            self.tree[node] = a[lo]
21            return
22        mid = (lo + hi) // 2
23        self._build(a, 2 * node, lo, mid)
24        self._build(a, 2 * node + 1, mid + 1, hi)
25        self.tree[node] = self.combine(self.tree[2 * node], self.tree[2 * node + 1])
26 
273 · Range query: prune, take, or split
28    def query(self, l: int, r: int) -> int:
29        """Aggregate over the closed range [l, r]."""
30        return self._query(1, 0, self.n - 1, l, r)
31 
32    def _query(self, node: int, lo: int, hi: int, l: int, r: int) -> int:
33        if r < lo or hi < l:          # disjoint
34            return self.identity
35        if l <= lo and hi <= r:       # fully covered
36            return self.tree[node]
37        mid = (lo + hi) // 2
38        return self.combine(
39            self._query(2 * node, lo, mid, l, r),
40            self._query(2 * node + 1, mid + 1, hi, l, r),
41        )
42 
434 · Point update: descend to leaf, recombine ancestors
44    def update(self, idx: int, value: int) -> None:
45        """Set a[idx] = value."""
46        self._update(1, 0, self.n - 1, idx, value)
47 
48    def _update(self, node: int, lo: int, hi: int, idx: int, value: int) -> None:
49        if lo == hi:
50            self.tree[node] = value
51            return
52        mid = (lo + hi) // 2
53        if idx <= mid:
54            self._update(2 * node, lo, mid, idx, value)
55        else:
56            self._update(2 * node + 1, mid + 1, hi, idx, value)
57        self.tree[node] = self.combine(self.tree[2 * node], self.tree[2 * node + 1])
Walkthrough
  1. self.tree is a flat list of 4n zeros with 1-based indexing; children of node are 2 * node and 2 * node + 1.
  2. combine is a @staticmethod and identity a class attribute, so a subclass overrides both to switch the aggregate (e.g. min with float("inf")).
  3. _build recurses to leaves (lo == hi), stores a[lo], and combines the halves bottom-up in O(n).
  4. _query prunes disjoint nodes (returns identity), takes fully covered nodes, and combines both children for partial overlap.
  5. _update follows the single root-to-leaf path for idx, then recombines every ancestor.
Complexity (this implementation)
time O(n) build; O(log n) query/update · space O(n)

Recursion depth is only O(log n) (~20 levels for n = 10^6), so Python's 1000-frame limit is never a concern — unlike O(n)-deep plain-BST recursions. Function-call overhead still makes this several times slower than the iterative version.

Language notes
  • Python ints are arbitrary precision, so there is no overflow concern for sums.
  • (lo + hi) // 2 is floor division; plain / would produce a float index.
  • The recursive helper pattern (query public wrapper, _query with node bounds) keeps the API clean.
Common mistakes in this language
  • Allocating 2 * n slots for the recursive layout instead of 4 * n.
  • Overriding combine to min but forgetting to override identity (must become float("inf")).
  • Calling query(l, r) with half-open semantics; this implementation is closed-inclusive on both ends.
Language differences that matter here
  • Overflow: C++ needs long long for large sums; JS/TS numbers silently lose integer precision past 2^53 (use BigInt); Python ints are arbitrary precision.
  • Genericity: the TS version injects the monoid through constructor generics; C++ would use a template parameter; Python and JS swap combine/identity by subclassing.
  • Identity for min/max: LLONG_MAX/LLONG_MIN in C++, Infinity/-Infinity in JS/TS, float("inf") in Python — forgetting to change it is the classic porting bug.
  • Recursion depth is O(log n) everywhere, so even Python's 1000-frame default limit is safe — but Python call overhead makes its iterative variant noticeably faster.

Complexity

OperationAverageWorstNote
AccessO(log n)O(log n)Single element = query(i, i).
SearchO(n)O(n)O(log n) tree descent for monotone aggregates (e.g. first prefix ≥ x).
Insert——Fixed size; rebuild in O(n).
Delete——Set to identity in O(log n).
UpdateO(log n)O(log n)
BuildO(n)O(n)
Range queryO(log n)O(log n)
Point updateO(log n)O(log n)
Range update (lazy)O(log n)O(log n)
SpaceO(n)4n slots with recursive 1-based layout, 2n with the iterative layout; lazy adds another array.

Advantages & disadvantages

Advantages
  • Handles any associative operation, not just invertible ones like sum.
  • Range updates via lazy propagation; O(log n) for every operation.
  • Supports advanced tricks: tree walks, persistent versions, merging, 2D variants.
Disadvantages
  • Memory 4n (or 2n iterative) versus n for a Fenwick tree.
  • Considerably more code; lazy propagation is error-prone under time pressure.
  • Constant factors are higher than a Fenwick tree for plain prefix sums.

Use cases

  • Range minimum/maximum/sum queries with point updates (Range Sum Query – Mutable).
  • Range add + range sum, range assign + range min (lazy).
  • Counting inversions or elements-less-than-x by indexing values instead of positions.
  • Sweep-line geometry (area of union of rectangles), scheduling with capacity constraints.
Use it when
  • Range queries interleaved with updates on an array of size up to about 10^6.
  • The aggregate is not invertible (min, max, gcd) so prefix sums cannot be subtracted.
  • Range updates are required — lazy propagation.
  • "First index where the running aggregate crosses a threshold" via tree descent.
Avoid it when
  • No updates — a Prefix Sum array or Sparse Table is simpler and faster.
  • Only prefix sums with point updates — a Fenwick Tree uses less memory and less code.
  • Queries are few (q · n is small) — brute force.

Alternatives

Fenwick TreeSparse TablePrefix SumInterval Tree
Compare: Prefix Sum vs Segment TreeCompare: Segment Tree vs Fenwick Tree

Common mistakes

  • Allocating 2n slots with the recursive 1-based layout — it needs 4n when n is not a power of two.
  • Returning 0 instead of the true identity for min/max queries (should be +∞/-∞).
  • Forgetting to push lazy tags before descending in a query, returning stale child values.
  • Multiplying a lazy add by the wrong interval length, or applying the tag to the node but not to lazy[node].
  • Off-by-one between closed [l, r] and half-open [l, r) conventions.

Interview patterns

  • Range Sum Query – Mutable: build, update, sumRange.
  • Count of smaller numbers after self / inversions: coordinate-compress values, iterate from the right, query prefix count, then point-add.
  • Range add + range sum with lazy propagation.
  • Skyline / rectangle union area via sweep line with a "count and covered length" segment tree.
  • Merge-sort tree or persistent segment tree for kth smallest in a range (advanced).
Interview questions on this
Mock interviews

Interview problems

Corporate Flight BookingsmediumRange Sum Query — MutablemediumRange XOR Queries with Updatesmedium