Segment tree¶
A tree over an array where every node stores an answer (minimum, sum, maximum, ...) for one range. Any range breaks into \(O(\log n)\) whole nodes, so range questions and single changes are both \(O(\log n)\).
| Point update | Range query | Build | Space |
|---|---|---|---|
| \(O(\log n)\) | \(O(\log n)\) | \(O(n)\) | \(\le 4n\) nodes |
The idea¶
The root of a segment tree covers the whole array, positions \(0..n-1\). Each node's range is split in half between its two children, down to the leaves, which hold single positions. Each node stores the answer for its range, here the minimum: the root stores the minimum of everything, its children the minimums of the two halves, and so on.
- Query \(\min(a[l..r])\): start at the root. A node whose range lies entirely inside \([l, r]\) answers with its stored value at once; a node entirely outside answers "infinity"; a node that overlaps partly asks its two children. At most four nodes per level are visited.
- Update \(a[i] = v\): change the leaf, then recompute the minimum in each ancestor on the way back up.
Anything that combines like minimum does (an associative operation: sum, max, gcd, product, "count of zeros") works the same way. With lazy propagation, whole ranges can be updated in \(O(\log n)\) too.
How it works¶
- Node 1 covers \([0, n-1]\); node \(k\) covering \([lo, hi]\) has children \(2k\) covering \([lo, mid]\) and \(2k+1\) covering \([mid+1, hi]\), where \(mid = \lfloor (lo + hi)/2 \rfloor\).
build: leaves take \(a[lo]\); inner nodes take the min of their children.query(l, r): no overlap → \(+\infty\); full cover → stored value; else min of the children's answers.update(i, v): recurse to the leaf for \(i\), set it, recompute on the way back.
Code¶
INF = float("inf")
class SegmentTree:
"""Range minimum over a[lo..hi] and point updates, both O(log n). Node 1 covers the whole array."""
def __init__(self, a):
self.n = len(a)
self.t = [0] * (4 * self.n)
self._build(1, 0, self.n - 1, a)
def _build(self, node, lo, hi, a):
if lo == hi:
self.t[node] = a[lo] # a leaf holds one value
return
mid = (lo + hi) // 2
self._build(2 * node, lo, mid, a)
self._build(2 * node + 1, mid + 1, hi, a)
self.t[node] = min(self.t[2 * node], self.t[2 * node + 1])
def update(self, i, value, node=1, lo=0, hi=None):
"""a[i] = value."""
if hi is None:
hi = self.n - 1
if lo == hi:
self.t[node] = value
return
mid = (lo + hi) // 2
if i <= mid:
self.update(i, value, 2 * node, lo, mid)
else:
self.update(i, value, 2 * node + 1, mid + 1, hi)
self.t[node] = min(self.t[2 * node], self.t[2 * node + 1]) # repair on the way back up
def query(self, l, r, node=1, lo=0, hi=None):
"""min(a[l..r]), both ends included."""
if hi is None:
hi = self.n - 1
if r < lo or hi < l: # no overlap
return INF
if l <= lo and hi <= r: # this node's range is inside [l, r]: use it whole
return self.t[node]
mid = (lo + hi) // 2
return min(self.query(l, r, 2 * node, lo, mid), self.query(l, r, 2 * node + 1, mid + 1, hi))
if __name__ == "__main__":
a = [5, 8, 6, 3, 2, 7, 2, 6]
st = SegmentTree(a)
print(st.query(0, 7), st.query(0, 2), st.query(1, 3), st.query(5, 5))
st.update(4, 9) # a[4]: 2 -> 9
print(st.query(3, 5), st.query(4, 5))
st.update(3, 10)
print(st.query(0, 4), st.t[1])
public class SegmentTree {
final int n;
final int[] t;
/** Range minimum over a[lo..hi] and point updates, both O(log n). Node 1 covers the whole array. */
SegmentTree(int[] a) {
n = a.length;
t = new int[4 * n];
build(1, 0, n - 1, a);
}
void build(int node, int lo, int hi, int[] a) {
if (lo == hi) { t[node] = a[lo]; return; } // a leaf holds one value
int mid = (lo + hi) / 2;
build(2 * node, lo, mid, a);
build(2 * node + 1, mid + 1, hi, a);
t[node] = Math.min(t[2 * node], t[2 * node + 1]);
}
/** a[i] = value. */
void update(int i, int value) { update(i, value, 1, 0, n - 1); }
void update(int i, int value, int node, int lo, int hi) {
if (lo == hi) { t[node] = value; return; }
int mid = (lo + hi) / 2;
if (i <= mid) update(i, value, 2 * node, lo, mid);
else update(i, value, 2 * node + 1, mid + 1, hi);
t[node] = Math.min(t[2 * node], t[2 * node + 1]); // repair on the way back up
}
/** min(a[l..r]), both ends included. */
int query(int l, int r) { return query(l, r, 1, 0, n - 1); }
int query(int l, int r, int node, int lo, int hi) {
if (r < lo || hi < l) return Integer.MAX_VALUE; // no overlap
if (l <= lo && hi <= r) return t[node]; // this node's range is inside [l, r]: use it whole
int mid = (lo + hi) / 2;
return Math.min(query(l, r, 2 * node, lo, mid), query(l, r, 2 * node + 1, mid + 1, hi));
}
public static void main(String[] args) {
SegmentTree st = new SegmentTree(new int[]{5, 8, 6, 3, 2, 7, 2, 6});
System.out.println(st.query(0, 7) + " " + st.query(0, 2) + " " + st.query(1, 3) + " " + st.query(5, 5));
st.update(4, 9); // a[4]: 2 -> 9
System.out.println(st.query(3, 5) + " " + st.query(4, 5));
st.update(3, 10);
System.out.println(st.query(0, 4) + " " + st.t[1]);
}
}
#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;
// Range minimum over a[lo..hi] and point updates, both O(log n). Node 1 covers the whole array.
struct SegmentTree {
int n;
vector<int> t;
explicit SegmentTree(const vector<int>& a) : n(a.size()), t(4 * a.size()) { build(1, 0, n - 1, a); }
void build(int node, int lo, int hi, const vector<int>& a) {
if (lo == hi) { t[node] = a[lo]; return; } // a leaf holds one value
int mid = (lo + hi) / 2;
build(2 * node, lo, mid, a);
build(2 * node + 1, mid + 1, hi, a);
t[node] = min(t[2 * node], t[2 * node + 1]);
}
// a[i] = value.
void update(int i, int value, int node = 1, int lo = 0, int hi = -1) {
if (hi == -1) hi = n - 1;
if (lo == hi) { t[node] = value; return; }
int mid = (lo + hi) / 2;
if (i <= mid) update(i, value, 2 * node, lo, mid);
else update(i, value, 2 * node + 1, mid + 1, hi);
t[node] = min(t[2 * node], t[2 * node + 1]); // repair on the way back up
}
// min(a[l..r]), both ends included.
int query(int l, int r, int node = 1, int lo = 0, int hi = -1) const {
if (hi == -1) hi = n - 1;
if (r < lo || hi < l) return INT_MAX; // no overlap
if (l <= lo && hi <= r) return t[node]; // this node's range is inside [l, r]: use it whole
int mid = (lo + hi) / 2;
return min(query(l, r, 2 * node, lo, mid), query(l, r, 2 * node + 1, mid + 1, hi));
}
};
int main() {
SegmentTree st({5, 8, 6, 3, 2, 7, 2, 6});
cout << st.query(0, 7) << " " << st.query(0, 2) << " " << st.query(1, 3) << " " << st.query(5, 5) << "\n";
st.update(4, 9); // a[4]: 2 -> 9
cout << st.query(3, 5) << " " << st.query(4, 5) << "\n";
st.update(3, 10);
cout << st.query(0, 4) << " " << st.t[1] << "\n";
}
Output for \(a = [5, 8, 6, 3, 2, 7, 2, 6]\): 2 5 3 7 (the minimums of \([0,7]\), \([0,2]\), \([1,3]\), \([5,5]\)); after
\(a[4] = 9\), 3 7; after \(a[3] = 10\), 5 2.
When to use it¶
- Range minimum / maximum / sum queries on changing data: game leaderboards over time windows, stock prices, scheduling with capacities.
- Range updates ("add 5 to every value in \([l, r]\)") with lazy propagation.
- Computational geometry: area of a union of rectangles, sweep-line counting.
- For sums only, a Fenwick tree is shorter. For a static array (no updates), a sparse table answers range minimum in \(O(1)\) after \(O(n \log n)\) preparation.
Common mistakes¶
- Array too small: with this layout, node numbers can reach almost \(4n\); allocate
4 * n. - Wrong "no answer" value: \(+\infty\) for min, \(-\infty\) for max, 0 for sum. Using 0 for min is a classic bug.
- Forgetting to recompute a parent after updating a child.
- Inclusive versus exclusive range ends; this page uses inclusive \([l, r]\).
Going deeper¶
Each part below starts closed; open the ones you want.
Sample walkthrough: min of a[1..6] in [5, 8, 6, 3, 2, 7, 2, 6]
[0..7] 2
/ \
[0..3] 3 [4..7] 2
/ \ / \
[0..1] 5 [2..3] 3 [4..5] 2 [6..7] 2
/ \ / \ / \ / \
5 8 6 3 2 7 2 6
\([1, 6]\) is covered by the whole nodes [1] (leaf 8), [2..3] (3), [4..5] (2) and [6] (leaf 2): \(\min(8, 3, 2, 2) = 2\). Every other node visited only passes the question down.
The math: why a query touches O(log n) nodes
Height. Ranges halve at each level, so the tree has height \(\lceil \log_2 n \rceil\).
At most 4 nodes per level. At any level, the nodes visited that only partly overlap \([l, r]\) can be only the ones containing \(l\) or \(r\): at most 2. Only they recurse, so at most \(2 \times 2 = 4\) nodes are visited on the next level. A query visits at most \(4 \lceil \log_2 n \rceil\) nodes and uses at most \(2\lceil \log_2 n \rceil\) whole nodes in its answer.
Space. With \(h = \lceil \log_2 n \rceil\), node numbers stay below \(2^{h+1} < 4n\).
Why associativity matters. A query combines whole-node answers in an order fixed by the tree, so the operation \(\oplus\) must satisfy \((x \oplus y) \oplus z = x \oplus (y \oplus z)\). Minimum, sum, product of matrices and gcd all qualify; average does not (store sum and count instead).
Lazy propagation. For "add \(d\) to \([l, r]\)", a fully covered node adds \(d\) to its stored minimum and remembers a pending \(+d\) for its children, pushed down only when a later operation needs them. Each update still touches \(O(\log n)\) nodes.
Watch it step by step
Small labels show each node's range; the number inside is its stored minimum.
Variations and related ideas
- Iterative (bottom-up) segment tree: leaves at \(n..2n-1\), parents at \(i/2\); about half the code and faster.
- Lazy propagation for range assignments and range additions.
- Persistent segment trees keep every old version by copying only the \(O(\log n)\) changed nodes; they answer "\(k\)-th smallest in a subarray".
- Merge sort tree: each node stores its range sorted; counts values \(\le x\) in a range in \(O(\log^2 n)\).
- Sparse table: static range minimum in \(O(1)\) per query.
See also¶
- Fenwick tree: simpler, for sums
- Binary heap: the same array-as-tree numbering
- Recursion
References¶
- M. de Berg, O. Cheong, M. van Kreveld, M. Overmars, Computational Geometry, 3rd ed., §10.3 (segment trees).
- S. Halim, F. Halim, Competitive Programming 3, 2013, Chapter 2 (segment tree).