Segment Tree
The general-purpose interval tree for logarithmic range queries and updates when Fenwick is too small.
Segment Tree
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
The segment tree is the contest default for dynamic interval queries. Once a problem stops being ``just prefixes'' and starts asking about arbitrary subarrays with updates, the segment tree is usually the first serious tool worth trying.
It is more general than a Fenwick tree, easier to customize than many advanced structures, and flexible enough to serve as the inner engine for techniques like heavy-light decomposition or offline divide-and-conquer optimizations.
When to Use It
Use it when:
queries are on arbitrary intervals rather than only prefixes,
updates are not limited to one simple prefix transformation,
the answer can be merged associatively from child intervals,
the array is dynamic enough that prefix sums or sparse tables are no longer sufficient.
Common examples are range sum, range min, range max, range gcd, and custom node states for DP-like transitions.
Core Idea
The array is recursively decomposed into halves. Each tree node stores the aggregate of one segment, and each internal node is just the merge of its two children.
That picture matters because any query interval can be decomposed into only \(O(\log n)\) disjoint tree segments. So instead of scanning every array element in \([l, r]\), we merge a small number of precomputed summaries.
Worked example.
If the array has eight elements and I query \([2, 7]\), the tree does not inspect six leaves one by one. It splits the query into a small set of covered nodes, merges their summaries, and ignores the rest of the tree completely.
Key Insight
The real power of a segment tree is not the tree shape itself. The power is that:
each node summarizes a contiguous interval,
every interval can be broken into a logarithmic number of node intervals,
the merge operation is local and reusable.
Once that viewpoint is clear, many ``advanced'' segment tree problems are just different choices of node state and merge logic.
Operations / Main Technique
The standard operations are:
build: initialize leaves, then pull values upward,
point update: change one leaf and recompute ancestors,
range query: collect the minimal set of disjoint nodes covering the interval.
Iterative vs recursive.
Both versions are useful:
the iterative version is short, cache-friendly, and great for plain point-update/range-query tasks,
the recursive version is often easier when lazy propagation or custom node states become complicated.
The reference code uses the iterative version because it is the cleanest baseline.
Correctness Intuition
Two invariants carry the whole structure:
every internal node stores the merge of its two children,
every query interval can be partitioned into disjoint node intervals from the tree.
Because the merge is associative, it does not matter how the interval was split during the recursion or iterative walk. The final merged answer is exactly the answer on the original interval.
Complexity Analysis
build: \(O(n)\),
point update: \(O(\log n)\),
range query: \(O(\log n)\),
memory: \(O(n)\), usually stored as about \(2n\) in the iterative layout.
The log factor comes from climbing up or touching at most one node per level on each side of the query.
Implementation
The reference code keeps an iterative sum tree with:
build from an array,
point assignment,
point add,
range sum query on an inclusive interval.
That is enough to illustrate the common layout. In practice, many contest trees differ only in two places: the node type and the merge rule.
Common Pitfalls
Mixing inclusive ranges with half-open ranges.
Using a merge that is not associative.
Forgetting that the iterative layout stores leaves starting at \(\texttt{n}\).
Reaching for a segment tree when the array is static and a sparse table would be simpler.
Writing a custom node merge without proving what each field actually means.
Variants / Extensions
lazy propagation for range updates,
segment tree beats for harder range chmin/chmax style problems,
persistent segment trees,
implicit segment trees for huge coordinates,
segment trees whose nodes store richer states such as max subarray, matrices, or DP transitions.
Most segment-tree-heavy problems are really in this section, not in the plain base tree.
Practice Problems
Dynamic range sum or range minimum queries.
Maximum subarray queries with point updates.
Heavy-light decomposition path queries with a segment tree as the path engine.
Problems where each segment tree node stores a small custom struct instead of one number.
References
Code
Contest-ready reference implementation for the idea explained above.
struct SegTree {
int n;
vector<long long> tree;
SegTree() : n(0) {}
explicit SegTree(const vector<long long>& values) { build(values); }
void build(const vector<long long>& values) {
n = (int)values.size();
tree.assign(2 * n, 0);
for (int i = 0; i < n; ++i) tree[n + i] = values[i];
for (int i = n - 1; i > 0; --i) tree[i] = tree[i << 1] + tree[i << 1 | 1];
}
void point_set(int pos, long long value) {
pos += n;
tree[pos] = value;
for (pos >>= 1; pos > 0; pos >>= 1) {
tree[pos] = tree[pos << 1] + tree[pos << 1 | 1];
}
}
void point_add(int pos, long long delta) {
pos += n;
tree[pos] += delta;
for (pos >>= 1; pos > 0; pos >>= 1) {
tree[pos] = tree[pos << 1] + tree[pos << 1 | 1];
}
}
long long range_sum(int left, int right) const {
long long left_result = 0, right_result = 0;
for (left += n, right += n; left <= right; left >>= 1, right >>= 1) {
if (left & 1) left_result += tree[left++];
if (!(right & 1)) right_result += tree[right--];
}
return left_result + right_result;
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.