Cosmos 仓库 Segment Tree 完全指南:区间查询与点更新的经典数据结构实现
Cosmos 仓库 Segment Tree 完全指南:区间查询与点更新的经典数据结构实现
Segment Tree(线段树)是 Cosmos 开源代码仓库中 data_structures 模块的核心数据结构之一,专门用于解决"数组多次区间查询 + 单点/区间修改"这类高频问题,例如求区间 [L, R] 之和(Range Sum Query)或区间最小值(Range Minimum Query,RMQ)。阅读完本文,你将掌握线段树的区间划分原理、数组化存储技巧、build/update/query 三大核心操作的递归实现与复杂度分析,并能直接参考仓库内 C++、Java、Python、Go、Scala、Ada 等多语言实现进行实战落地。
什么是 Segment Tree
线段树是一棵用于存储区间(segment / interval)信息的二叉树。其核心思想是:把整个数组不断对半切分,用树节点分别代表每个子区间,从而让任意区间的查询与修改都能在对数时间内完成。
以数组 A(大小为 N)及其对应的线段树 T 为例,仓库文档 code/data_structures/src/tree/space_partitioning_tree/segment_tree/README.md 给出了三条基本性质:
- 根节点代表整个数组区间
A[0:N−1]; - 叶子节点代表单个元素
A[i](0≤i<N); - 内部节点代表两个子区间的并集
A[i:j](0≤i<j<N)。
例如,根节点代表 A[0:N−1],它的左右两个孩子分别代表 A[0:(N−1)/2] 与 A[(N−1)/2+1:(N−1)],每一步都把区间一分为二。由此可以得到线段树的结构参数:
- 树高为 log₂N;
- 叶子节点共 N 个(对应 N 个数组元素);
- 内部节点共 N−1 个;
- 节点总数为 2×N−1。
需要特别强调的是:线段树一旦建好,结构便不可改变——我们只能更新节点的值,不能增删节点、改变树的形态。它对外只暴露两种操作:
- Update:更新数组 A 中某个元素,并同步反映到线段树上;
- Query:对任意区间
[L, R]发起查询,返回该区间对应的答案(如最小值、最大值、区间和)。
线段树的存储方式:用线性数组装下一棵二叉树
线段树本质是二叉树,因此可以直接用一维数组来存储,无需显式使用指针。关键约定如下:
- 若当前节点在数组中的下标为
node,则左孩子为2*node,右孩子为2*node+1(README 中 C++ 版采用 1-based 下标约定); - Java 版 segment_tree.java 采用 0-based 下标约定,左孩子为
2*si+1、右孩子为2*si+2; - 数组开多大?从源码看存在两种常见策略:
- C++ 版 segment_tree_rmq.cpp 直接开
4*N的数组(const int maxn = 1e5 + 1,ll segtree[4*n]),这是竞赛中最稳妥的估算(2×N−1 的节点上限不超过 4N); - Java 版则按树高精确计算:
max_size = 2 * 2^ceil(log2(N)) − 1,其中ceil(log2(N))即树高。
- C++ 版 segment_tree_rmq.cpp 直接开
建树前还有一个关键决策:节点里到底存什么? 这完全取决于问题本身。README 明确指出:若问题是求 [L, R] 区间和,则每个内部节点存其两个孩子之和;若问题是求区间最小值(RMQ),则每个节点存两个孩子中的较小值。这个"合并规则"(merge 规则)是线段树唯一需要针对问题定制的部分。
建树(build):自底向上的递归构造
线段树采用递归 + 自底向上的方式构建:从叶子出发逐层合并,直到根节点代表整个数组。每个叶子存放单个元素,内部节点则通过合并两个孩子节点的数据生成,合并规则随问题而异。
README 给出的求和版本 build 代码如下:
void build(int node, int start, int end)
{
if(start == end)
{
// Leaf node will have a single element
tree[node] = A[start];
}
else
{
int mid = (start + end) / 2;
// Recurse on the left child
build(2*node, start, mid);
// Recurse on the right child
build(2*node+1, mid+1, end);
// Internal node will have the sum of both of its children
tree[node] = tree[2*node] + tree[2*node+1];
}
}
这段代码从根节点出发,递归进入左、右孩子,直到抵达叶子节点(start == end);随后在回溯过程中更新路径上的所有节点。node 是当前处理节点,start 与 end 表示该节点对应的区间。build 的复杂度为 O(N)——每个节点恰好被访问一次。
仓库中同思路的多语言实现可以直接对照阅读:
- C++ 求和版:segment_tree_sum.cpp(使用指针动态建树);
- Python 求和版:segment_tree_sum.py;
- Java 求和版:segment_tree.java,其
constructSTUtil与 README 逻辑一一对应; - Scala 版:segment_tree.scala。
点更新(update):定位叶子并回溯修正
更新操作的目标是:修改数组元素 A[idx],同时让线段树上所有覆盖该位置、受影响的祖先节点同步更新。做法是:根据当前区间判断 idx 落在左孩子还是右孩子区间,递归下潜直至叶子;更新叶子后,再自底向上重算路径上每个内部节点的值。
README 给出求和版 update 如下:
void update(int node, int start, int end, int idx, int val)
{
if(start == end)
{
// Leaf node
A[idx] += val;
tree[node] += val;
}
else
{
int mid = (start + end) / 2;
if(start <= idx and idx <= mid)
{
// If idx is in the left child, recurse on the left child
update(2*node, start, mid, idx, val);
}
else
{
// if idx is in the right child, recurse on the right child
update(2*node+1, mid+1, end, idx, val);
}
// Internal node will have the sum of both of its children
tree[node] = tree[2*node] + tree[2*node+1];
}
}
注意这里更新语义是 A[idx] = A[idx] + val(增量更新)。由于每次只沿一条从根到叶子的路径下潜,路径长度就是树高,update 的复杂度为 O(log N)。
仓库中的 Java 实现 segment_tree.java 还展示了另一种常见语义——替换更新:先计算新旧值之差 diff = new_val - arr[i],再沿路径把每个节点都加上 diff,同时更新原数组 arr[i] = new_val。这两种写法(增量 vs 替换)对应不同题目要求,阅读时请注意区分。
区间查询(query):三种区间关系的判定
查询的目标是求 [l, r] 的答案。从根开始递归,每个节点面临三种情况:
- 完全覆盖:节点代表的区间完全落在
[l, r]内 → 直接返回该节点的值; - 完全无关:节点代表的区间与
[l, r]无交集 → 直接返回"空值"(求和返回 0,求最小值返回INT_MAX/LLONG_MAX); - 部分重叠:节点区间与
[l, r]部分相交 → 递归查询左、右孩子,再按合并规则汇总。
README 给出的求和版 query 如下:
int query(int node, int start, int end, int l, int r)
{
if(r < start or end < l)
{
// range represented by a node is completely outside the given range
return 0;
}
if(l <= start and end <= r)
{
// range represented by a node is completely inside the given range
return tree[node];
}
// range represented by a node is partially inside and partially outside the given range
int mid = (start + end) / 2;
int p1 = query(2*node, start, mid, l, r);
int p2 = query(2*node+1, mid+1, end, l, r);
return (p1 + p2);
}
query 的复杂度为 O(log N):虽然在最坏情况下递归访问的节点数约为 4·log₂N 个,但渐近上界仍是 O(log N)。
完整示例:区间求和 + 点更新
README 用一个典型题目串起了上述全部操作:
给定大小为 N 的数组 A 与若干次操作,共有两种查询:
- Update:给定
idx与val,令A[idx] = A[idx] + val;- Query:给定
l与r,返回A[l] + A[l+1] + … + A[r],其中0≤l≤r<N。
解题思路分两步走:
第一步,确定节点存储内容。 题目要求区间和,因此每个节点存储"其代表区间内所有元素之和"。
第二步,依次实现 build / update / query。 即上文给出的三段代码。
这正好对应仓库中可直接运行的最小完整实现:
- C++:segment_tree_sum.cpp——指针式动态建树,支持
add(点更新)与ask(区间求和)两种命令,根区间甚至可以覆盖负数域(root = new node(-size, size)); - Python:segment_tree_sum.py;
- Go:segment_tree_sum.go;
- Ruby:segment_tree_sum.rb。
变体一:Range Minimum Query(RMQ)与"带更新"版本
当问题从"求和"变为"求区间最小值"时,线段树的骨架完全不变,只需要修改两处:
- 建树合并规则:
tree[node] = min(tree[left], tree[right]); - 查询的"空值":完全无关时返回极大值
LLONG_MAX(C++ 版 segment_tree_rmq.cpp 的做法),这样与真实最小值比较时不会污染结果。
C++ 版 segment_tree_rmq.cpp 直接以宏 #define min(a, b) ((a) < (b) ? (a) : (b)) 实现最小值合并,并使用 ll segtree[4*n] 定长数组,文件末尾还附带了完整的测试用例:
5 2
3 4 2 1 5
1 2 → Result is :3
2 5 → Result is :1
此外,仓库还提供了两版"带更新"的 RMQ:
- segment_tree_rmq_with_update.cpp:节点为指针结构体,每个节点记录
index(区间最小值的下标)与interval(区间端点),query 返回的是最小元素的下标而非值,update 采用增量语义(array[L] += value),并实现了析构函数递归释放内存; - segment_tree_rmq.py:Python 版,支持
q(查询最小值)与u(更新)两种交互命令,节点数组大小按2 * 2^(ceil(log2(n))+1) − 1预分配。
变体二:Lazy Propagation(懒标记区间更新)
当题目要求对整个区间 [l, r] 批量加一个值(而不是单点更新)时,朴素做法需要更新 O(N) 个点,退化为 O(N·log N)。懒标记(lazy propagation) 通过"延迟下推"把区间更新的复杂度压回 O(log N)。
其核心思想是:当节点区间被更新区间完全覆盖时,不立刻递归更新其所有子孙,而是把更新量暂存在该节点的 lazy 标记中,等将来查询或更新真正下潜到该子树时,再一次性把积累的标记"推下去"并结算。
仓库提供两份可直接对照的完整实现:
- C++:segment_tree_lazy_propagation.cpp——
updateRange与queryRange都先检查lazy[node],用tree[node] += (end - start + 1) * lazy[node]结算当前节点,再把标记分发给两个孩子;main 函数演示了建树 → 区间查询 → 区间更新 → 再次查询的完整流程; - Java:lazy_segment_tree.java——同样的懒标记逻辑,
updateRangeUtil与getSumUtil双函数分别处理区间更新与区间求和,main 中演示了"把[1,5]全部加 10 后查询[1,3]的和"。
变体三:持久化线段树(Persistent Segment Tree)与区间第 K 小
持久化线段树解决了"回到历史版本查询"的问题。仓库中的 persistent_segment_tree_sum.cpp 是完全持久化(fully persistent)实现:每次 add 操作都从指定历史版本克隆一条路径上的节点(new node(root[version]) 复制根,路径上的子节点通过拷贝构造 new node(vertexToClone) 复用旧节点),新版本存入 root[currentVersion];查询时用 ask(root[version], L, R) 读取任意历史版本的区间和。内存开销为 O(n·log size),每次操作 O(log size)。
在此基础上,segment_tree_kth_statistics_on_segment.cpp 把持久化线段树升级为主席树(可持久化权值线段树),解决"区间第 K 小 / 某值排名"问题:order_of_key(l, r, x) 用两个版本根的差值统计 [l, r] 内小于等于 x 的元素个数,find_by_order(l, r, x) 在左右子树计数差值的引导下二分下潜找到第 x 小的值。这是线段树在竞赛与算法面试中的经典进阶用法。
复杂度与适用性总结
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| build | O(N) | 每个节点访问一次,自底向上合并 |
| 点更新 update | O(log N) | 沿根到叶子的单条路径回溯 |
| 区间查询 query | O(log N) | 递归中三种区间关系判定 |
| 区间更新(懒标记) | O(log N) | lazy 延迟下推,避免全量更新 |
| 持久化 add / ask | O(log size) | 每次沿路径克隆节点,空间 O(n·log size) |
线段树的使用场景非常明确:同一数组上存在大量交替的区间查询与元素修改。若只有查询没有修改,前缀和、稀疏表(Sparse Table)往往更简单;若修改是全局性的、无需精细区间操作,树状数组(Fenwick Tree)也可能是更轻量的选择。当题目同时要求"区间查询 + 单点/区间更新"时,线段树才是最优解。
Cosmos 仓库在 code/data_structures/src/tree/space_partitioning_tree/segment_tree/ 目录下集中提供了 15 份可运行实现,覆盖 C++、Java、Python、Go、Ruby、Scala、Ada(segment_tree_rmq.adb)共 7 种语言,从最基础的区间和、区间最小值,到懒标记区间更新、持久化与主席树一应俱全。读者可以按"求和 → RMQ → 懒标记 → 持久化"的顺序逐份阅读,把线段树的每个变体都吃透。