Segment tree
Range queries for any associative operation, with point updates or, with lazy propagation, whole-range updates. per operation.
When
A Fenwick tree is not enough when the operation has no inverse (minimum, maximum, gcd) or when a node must store something composite, such as "maximum subarray sum".
The idea
A complete binary tree over the array: the leaves are the elements, and each internal node holds the combination of its two children. Any splits into nodes, at most two per level.
The first version is iterative, bottom-up: leaves at positions , the parent of is . It works for every , not only powers of 2. It keeps two results, left and right, so that it stays correct for non-commutative operations (e.g. function composition).
For a different operation you change only combine and IDENTITY: for sums, and a + b; for maximum, LLONG_MIN and max.
Lazy propagation. When an update covers a whole range ("add to "), we do not go down to the leaves. Where a node is covered entirely, we update its sum by and note in lazy that its children are owed . The debt is passed to the children (push) only when we need to go down.
Pitfalls
- The recursive version needs an array of size , not .
Range Updates and Sumsalso has "set the whole range to ". Thenlazyholds a pair (assign, add), and an assignment cancels any addition below it. The order of application inapplyis the whole difficulty.- In
Hotel Queriesyou want a position, not a value: "the first room with capacity ". Walk down from the root, always left if the left child has maximum . That is , not with a binary search on top.
Code
No main: it goes below the #include lines, using namespace std and using ll = long long.
// Segment tree, iterative (bottom-up), for any associative operation with an identity.
// Here: point assignment and range minimum on [l, r], 0-indexed. O(log n) per operation.
// Change combine() and IDENTITY for sums, max, gcd, ...
struct SegmentTree {
static constexpr ll IDENTITY = LLONG_MAX;
int n;
vector<ll> t;
static ll combine(ll a, ll b) {
return min(a, b);
}
SegmentTree(const vector<ll>& a) : n(a.size()), t(2 * a.size(), IDENTITY) {
for (int i = 0; i < n; i++) {
t[n + i] = a[i];
}
for (int i = n - 1; i >= 1; i--) {
t[i] = combine(t[2 * i], t[2 * i + 1]);
}
}
void set(int i, ll v) {
i += n;
t[i] = v;
while (i > 1) {
i /= 2;
t[i] = combine(t[2 * i], t[2 * i + 1]);
}
}
ll query(int l, int r) {
ll left = IDENTITY;
ll right = IDENTITY;
l += n;
r += n + 1;
while (l < r) {
if (l & 1) {
left = combine(left, t[l]);
l++;
}
if (r & 1) {
r--;
right = combine(t[r], right);
}
l /= 2;
r /= 2;
}
return combine(left, right);
}
};
Tested on 500 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).
// Segment tree with lazy propagation: add v to every element of [l, r], sum of [l, r].
// 0-indexed, recursive, O(log n) per operation.
// lazy[node] = value already added to tree[node] but not yet pushed to its children.
struct LazySegmentTree {
int n;
vector<ll> tree;
vector<ll> lazy;
LazySegmentTree(const vector<ll>& a) : n(a.size()), tree(4 * a.size() + 4, 0), lazy(4 * a.size() + 4, 0) {
if (n > 0) {
build(a, 1, 0, n - 1);
}
}
void build(const vector<ll>& a, int node, int l, int r) {
if (l == r) {
tree[node] = a[l];
return;
}
int mid = (l + r) / 2;
build(a, 2 * node, l, mid);
build(a, 2 * node + 1, mid + 1, r);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
void apply(int node, int l, int r, ll v) {
tree[node] += v * (r - l + 1);
lazy[node] += v;
}
void push(int node, int l, int r) {
if (lazy[node] != 0) {
int mid = (l + r) / 2;
apply(2 * node, l, mid, lazy[node]);
apply(2 * node + 1, mid + 1, r, lazy[node]);
lazy[node] = 0;
}
}
void add(int ql, int qr, ll v, int node, int l, int r) {
if (qr < l || r < ql) {
return;
}
if (ql <= l && r <= qr) {
apply(node, l, r, v);
return;
}
push(node, l, r);
int mid = (l + r) / 2;
add(ql, qr, v, 2 * node, l, mid);
add(ql, qr, v, 2 * node + 1, mid + 1, r);
tree[node] = tree[2 * node] + tree[2 * node + 1];
}
ll sum(int ql, int qr, int node, int l, int r) {
if (qr < l || r < ql) {
return 0;
}
if (ql <= l && r <= qr) {
return tree[node];
}
push(node, l, r);
int mid = (l + r) / 2;
return sum(ql, qr, 2 * node, l, mid) + sum(ql, qr, 2 * node + 1, mid + 1, r);
}
void add(int l, int r, ll v) {
add(l, r, v, 1, 0, n - 1);
}
ll sum(int l, int r) {
return sum(l, r, 1, 0, n - 1);
}
};
Tested on 500 random cases against a slow, obviously correct solution, with AddressSanitizer and UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).
Practice on CSES
In order: the first is the plain application, the rest need a twist.
- Dynamic Range Minimum Queries · Range Queries
- Hotel Queries · Range Queries
- Subarray Sum Queries · Range Queries
- Range Updates and Sums · Range Queries
More in the USACO Guide
- Point Update Range Sum · usaco.guide/gold/PURS
- Range Update Range Query · usaco.guide/plat/RURQ
In English, with more problems per level.