01 /
The one-sentence essence
Build a balanced binary tree where each node holds the aggregate of a range — sum, min, max, gcd, whatever. Any range decomposes into O(log N) canonical pieces that already live as nodes, so every range query and every point update is O(log N) instead of O(N).
Problemrange sum + point updateInput[2,5,1,4,9,3,7,6]Query[1,5]Updatea[3] = 10
Array of length 8. We'll build a binary tree where every node stores the sum of a contiguous range.
step
0
/
36
phase
build
live
—
0 /
36
# node covers [l, r]; agg = sum (or min / max / gcd / …)def build(node, l, r):if l == r: tree[node] ← arr[l]; returnm ← (l + r) // 2build(2·node, l, m); build(2·node+1, m+1, r)tree[node] ← tree[2·node] + tree[2·node+1]# query [ql, qr] — sum the canonical pieces inside itdef query(node, l, r, ql, qr):if qr < l or r < ql: return 0if ql ≤ l and r ≤ qr: return tree[node]m ← (l + r) // 2return query(2·node, l, m, ql, qr) + query(2·node+1, m+1, r, ql, qr)
"range sum / min / max / gcd with point updates"
The textbook trigger. The array changes (point update), and you keep asking for the aggregate over arbitrary ranges. Prefix sum is a no-update sibling; segment tree is its mutable cousin. If updates never happen, prefix sum is simpler and tighter.
"count smaller / count of range sum"
The classic "inversions" family (LC 315, 327, 493) — sort or coordinate-compress the relevant key, then sweep and maintain a frequency segment tree. Each new element contributes a range-count query on what came before.
"range update + range query"
The grown-up variant. Add lazy propagation: each node stores a pending update for its subtree that's applied only when the recursion descends through it. Same O(log N), now both operations are ranged.
"interval / event / coverage with mutation"
Coordinate-compress the unique x-positions into a small array, then the segment tree maintains the live status (count, max height, etc.) at each compressed position. Skyline, rectangle coverage, calendar booking — all collapse to this.
i.
Forgetting the +1 in the right half.
The recursion is build(2·node, l, m) and
build(2·node+1, m+1, r) — the right child starts at m+1, not
m. Off-by-one here gives a tree that double-counts arr[m]
or silently loses it depending on which half you bias.
ii.
Reaching for prefix sum first, then needing updates.
Prefix sum is O(1) per query but O(N) per update. The moment the problem says "now change arr[i]", you have to rebuild — at which point a segment tree (or a Fenwick tree for sum specifically) wins. Recognize the mutation requirement up front.
iii.
Sizing the tree array wrong.
A safe allocation for the flat array is 4·N. The exact bound is
2·next_power_of_two(N), but allocating 4·N avoids the math and the rare case where 2N is one short. Forgetting this on a tight bound produces an out-of-range write that's painful to debug.
Four problems, ordered by difficulty. No solutions here, by design.
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。