线段树
01 / 一句话本质
在一棵平衡二叉树上,每个节点持有一段区间的聚合值 —— 求和、最小、最大、gcd 都行。任意区间都能拆成 O(log N) 个已经存在为节点的「典型片段」, 因此区间查询和点更新都是 O(log N),不再是 O(N)。
题目区间和 + 单点修改输入[2,5,1,4,9,3,7,6]查询[1,5]修改a[3] = 10
长度为 8 的数组。我们构造一棵二叉树,每个节点存储某个连续区间的 和。
步
0 / 36
阶段
构造
实时
—
0 / 36
02 / 模式骨架
# 节点覆盖 [l, r];agg = 求和 (或 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]# 查询 [ql, qr] —— 把里面的典型片段累加def 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)
03 / 什么时候用这个模式
"区间和 / 最小 / 最大 / gcd + 点更新"
最教科书式的信号。数组会变(点更新),但你仍然要在任意区间上拿到聚合值。 前缀和是不可变版本的兄弟,线段树是它的可变表亲。如果根本不需要更新,前缀和更简洁。
"逆序对 / 区间和的个数"
经典的「逆序对」一族(LC 315、327、493)—— 把关键键值排序或离散化后扫一遍, 维护一棵频率线段树。每个新元素都做一次「之前看过的范围里有多少」的区间计数。
"区间更新 + 区间查询"
进阶版。加上懒标记:每个节点存一个待下推到子树的修改,只有当递归经过它时才下放。 同样的 O(log N),只是两个操作都是区间级了。
"带修改的区间 / 事件 / 覆盖"
把所有用到的 x 坐标做离散化,挤进一个小数组里,线段树就维护每个离散位置上的当前状态 (计数、最高高度等)。天际线、矩形覆盖、日程预订 —— 全部塌到这套机制上。
04 / 常见坑
i.
右半区间忘记加 1。
递归是
build(2·node, l, m) 和 build(2·node+1, m+1, r) —— 右孩子从 m+1 开始,不是 m。这里偏一,会让树重复计算 arr[m] 或悄悄把它漏掉,具体看你偏向哪一半。ii.
先用了前缀和,再发现要更新。
前缀和每次查询 O(1),但每次更新 O(N)。题目一旦说「现在改
arr[i]」, 你就得重新构建 —— 这时线段树(或对求和而言,树状数组)赢。 一开始就要识别出是否有可变需求。iii.
把树数组开小了。
稳妥的开法是
4·N。精确界是 2·下一个2的幂(N), 但开 4·N 直接避开了这套数学,也避开了 2N 差一格的罕见情况。开小了就会越界写,调试很痛苦。05 / 去 LeetCode 上练习
四道题,按难度排序。这里有意不放解答。