Cosmos 仓库 Segment Tree 完全指南:区间查询与点更新的经典数据结构实现

原创2026-09-22 22:31:411,930 阅读
文章标签:教程示例工程

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 给出了三条基本性质:

  1. 根节点代表整个数组区间 A[0:N−1];
  2. 叶子节点代表单个元素 A[i](0≤i<N);
  3. 内部节点代表两个子区间的并集 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)) 即树高。

建树前还有一个关键决策:节点里到底存什么? 这完全取决于问题本身。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)——每个节点恰好被访问一次。

仓库中同思路的多语言实现可以直接对照阅读:

点更新(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] 的答案。从根开始递归,每个节点面临三种情况:

  1. 完全覆盖:节点代表的区间完全落在 [l, r] 内 → 直接返回该节点的值;
  2. 完全无关:节点代表的区间与 [l, r] 无交集 → 直接返回"空值"(求和返回 0,求最小值返回 INT_MAX/LLONG_MAX);
  3. 部分重叠:节点区间与 [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 与若干次操作,共有两种查询:

  1. Update:给定 idx 与 val,令 A[idx] = A[idx] + val;
  2. Query:给定 l 与 r,返回 A[l] + A[l+1] + … + A[r],其中 0≤l≤r<N。

解题思路分两步走:

第一步,确定节点存储内容。 题目要求区间和,因此每个节点存储"其代表区间内所有元素之和"。

第二步,依次实现 build / update / query。 即上文给出的三段代码。

这正好对应仓库中可直接运行的最小完整实现:

变体一: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 → 懒标记 → 持久化"的顺序逐份阅读,把线段树的每个变体都吃透。

登录后查看全文
cosmos