cp-algorithms 线段树（Segment Tree）完全指南：从区间求和到持久化与二维扩展

文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载线段树Segment Tree是 cp-algorithms 仓库中数据结构章节的核心内容之一它把数组区间信息组织成一棵二叉树从而在O(log n)时间内同时支持区间查询与单点乃至整段区间修改。本篇指南以 src/data_structures/segment_tree.md 为主体骨架完整覆盖从最简求和线段树的构建、查询、更新与内存优化到最大值/次数统计、GCD/LCM、第 k 个零、最大和子段等高级查询再到 Merge Sort Tree、Lazy Propagation 区间更新、二维推广、持久化与动态线段树的全套实现并穿插仓库中 test/test_segment_tree.cpp 的实测验证。读完你将能够独立实现并驾驭线段树这一通用数据结构应对绝大多数区间问题。什么是线段树核心思想与复杂度线段树在二叉树的每个节点上存储数组某个连续区间的信息。它可以高效回答形如计算 $a[l \dots r]$ 的和、查询区间最小值的查询并在O(log n)时间内支持两种修改替换单个元素甚至修改整个子段如把 $a[l \dots r]$ 全部赋为某值或给整段加上一个数。线段树是一种极其灵活的数据结构可以解决的问题非常广泛它还能支持更复杂的操作与查询见本文高级版本各节并可自然推广到更高维度——例如二维线段树能在O(log² n)时间内回答矩阵某个子矩形的求和或最小值查询。线段树最重要的性质之一内存是线性的。对长度为 n 的数组标准实现只需 4n 个节点。一个线段树在每个节点上需要明确两件事节点存储的值例如求和线段树中节点存储其区间 $[l, r]$ 的元素和合并merge操作如何将左右两个兄弟节点合并为父节点。例如求和线段树中把区间 $[l_1, r_1]$ 与 $[l_2, r_2]$ 的节点合并成 $[l_1, r_2]$ 时直接把两个节点的值相加。叶子节点对应原始数组中恰好一个元素 $a[i]$其值即该元素本身。最简形态求和线段树问题定义如下给定数组 $a[0 \dots n-1]$线段树需要能在 O(log n) 时间内计算任意区间 $\sum_{il}^r a[i]$并在 O(log n) 时间内执行单点赋值 $a[i] x$。这相比朴素做法是显著改进普通数组更新 O(1)、查询 O(n)前缀和数组查询 O(1)、但更新要 O(n) 地重建前缀和。树的结构与节点数量上界采用分治思想先计算并存储整个数组 $a[0 \dots n-1]$ 的和作为根然后把数组分成两半 $a[0 \dots (n-1)/2]$ 与 $a[(n1)/2 \dots n-1]$ 各存一个和每半再二分直到所有段长度为 1。这些段形成一棵二叉树根是 $a[0 \dots n-1]$每个非叶节点恰有两个孩子——这就是线段树名称的由来尽管多数实现并不显式构建这棵树。由节点数逐层翻倍可知最坏情况下节点总数约 $1 2 4 \dots 2^{\lceil\log_2 n\rceil} 4n$。当 n 不是 2 的幂时树的某些层不会被填满这一点在实现时需要留意。树高为 O(log n)因为从根到叶子每走一步区间长度大约减半。构建构建从叶子层开始逐层向上先给叶子节点赋各自对应元素值再用merge函数逐层算出上一层的值直到根。用递归描述则相反对非叶节点先递归构建两个孩子再把孩子的值合并。以根为起点调用即可得到整棵树。若 merge 是常数时间构建复杂度为 O(n)merge 恰好被调用 n−1 次即内部节点数。区间求和查询假设当前位于覆盖区间 $a[tl \dots tr]$ 的顶点查询目标是 $a[l \dots r]$共有三种情况完全相等若 $a[l \dots r] a[tl \dots tr]$直接返回该顶点预存的和完全落入一个孩子若查询区间完全落在左孩子 $a[tl \dots tm]$ 或右孩子 $a[tm1 \dots tr]$其中 $tm (tl tr) / 2$则递归到对应孩子继续横跨两个孩子此时需要向左右两个孩子各发一次递归调用分别求出与查询区间的交集的答案再相加。也就是说查询过程是沿树遍历只访问必要的分支并复用节点预存的和。以数组 $a [1, 3, -2, 8, -7]$ 上计算 $\sum_{i2}^4 a[i]$ 为例结果是 $-2 1 -1$下图中的着色顶点即被访问的节点绿色节点的值被直接采用为什么是 O(log n)可以归纳证明每一层最多只访问 4 个顶点第一层只有根显然成立若当前层访问不超过 2 个顶点下一层至多 4 个每个顶点最多发起两次递归若当前层访问 3 或 4 个顶点中间的那些顶点对应区间会被查询区间完全覆盖不会再发起递归只有最左与最右两个顶点可能产生递归调用因此下一层仍满足至多 4 个。最终最多访问 $4\log n$ 个顶点即 O(log n)。直观地说查询相当于把输入区间划分成若干已预存的子段这些子段只需 O(log n) 个。单点更新由于线段树的每一层都构成数组的一个划分元素 $a[i]$ 每层只属于一个段因此只需更新 O(log n) 个顶点递归地进入包含 $a[i]$ 的那个孩子返回时像 build 一样用两个孩子之和重算当前节点。以下图为例执行更新 $a[2] 3$绿色顶点即需要访问和更新的节点数组存储实现存储方式决定实现效率。可以定义Vertex结构体存储区间边界、和与指向孩子的指针但会带来大量冗余指针。更好的做法是隐式数据结构只用一维数组t[]存和与二叉堆类似。采用 1 起始索引根在索引 1两个孩子在 2 和 3依此类推顶点 i 的左孩子恰好在 $2i$、右孩子在 $2i1$父节点在 $i/2$整数除法。这样无需显式存储树结构只需一个存各段和的数组。虽然某些数组元素可能不对应树中真实顶点但实现并不复杂我们统一分配 4 倍大小int n, t[4*MAXN];构建函数递归实现参数为输入数组a[]、当前顶点索引v及当前段边界tl、tr主程序以根参数v 1, tl 0, tr n - 1调用void build(int a[], int v, int tl, int tr) { if (tl tr) { t[v] a[tl]; } else { int tm (tl tr) / 2; build(a, v*2, tl, tm); build(a, v*21, tm1, tr); t[v] t[v*2] t[v*21]; } }求和查询同样是递归函数接收当前顶点信息v,tl,tr和查询边界l,r。为了简化代码函数总是发起两次递归调用多余的那次会满足l r在函数开头用l r检查兜底返回 0int sum(int v, int tl, int tr, int l, int r) { if (l r) return 0; if (l tl r tr) { return t[v]; } int tm (tl tr) / 2; return sum(v*2, tl, tm, l, min(r, tm)) sum(v*21, tm1, tr, max(l, tm1), r); }更新函数除当前顶点信息外还需接收要修改的位置与新值void update(int v, int tl, int tr, int pos, int new_val) { if (tl tr) { t[v] new_val; } else { int tm (tl tr) / 2; if (pos tm) update(v*2, tl, tm, pos, new_val); else update(v*21, tm1, tr, pos, new_val); t[v] t[v*2] t[v*21]; } }内存高效实现Euler 遍历编号上述数组t按照 BFS层序编号孩子为 $2v$、$2v1$。但 n 不是 2 的幂时会有索引跳空、部分数组闲置真实线段树只需要 $2n - 1$ 个顶点却可能占用 4n 内存。可以采用前序遍历编号进一步压缩顶点 v 负责区间 $[l, r]$令 $mid (lr)/2$则左孩子索引必为 $v1$左孩子子树共有 $2 \times (mid - l 1) - 1$ 个顶点因此右孩子索引为 $v 2 \times (mid - l 1)$。按此编号可将内存需求降到2n。高级版本更复杂的查询线段树非常灵活可按需演变为多种形态。仓库测试 test/test_segment_tree.cpp 将下述各实现按命名空间独立编译逐一用断言验证正确性可作为学习与复现的对照。求最大值最小值把 build 与 update 中对t[v]的计算从两子之和改为两子取最大值并把查询返回值的求和替换为求最大值即可改为求最小值同理。下文将直接给出一个更复杂的变体实现。求最大值及其出现次数每个顶点存储一对数区间最大值及其出现次数。合并两个孩子用独立的combine函数构建、查询、更新都会用到它常数时间内完成pairint, int t[4*MAXN]; pairint, int combine(pairint, int a, pairint, int b) { if (a.first b.first) return a; if (b.first a.first) return b; return make_pair(a.first, a.second b.second); } void build(int a[], int v, int tl, int tr) { if (tl tr) { t[v] make_pair(a[tl], 1); } else { int tm (tl tr) / 2; build(a, v*2, tl, tm); build(a, v*21, tm1, tr); t[v] combine(t[v*2], t[v*21]); } } pairint, int get_max(int v, int tl, int tr, int l, int r) { if (l r) return make_pair(-INF, 0); if (l tl r tr) return t[v]; int tm (tl tr) / 2; return combine(get_max(v*2, tl, tm, l, min(r, tm)), get_max(v*21, tm1, tr, max(l, tm1), r)); } void update(int v, int tl, int tr, int pos, int new_val) { if (tl tr) { t[v] make_pair(new_val, 1); } else { int tm (tl tr) / 2; if (pos tm) update(v*2, tl, tm, pos, new_val); else update(v*21, tm1, tr, pos, new_val); t[v] combine(t[v*2], t[v*21]); } }对应实测位于 test/test_segment_tree.cpptest_section_maximum_and_count例如对a {4, 7, 1, 3, 3, 0, 5, 9, 0, 7}区间[2,6]的最大值为 5、出现 1 次把位置 6 更新为 2 后区间[2,6]的最大值变为 3 且出现 2 次。求区间 GCD / LCM与求和/最小/最大线段树完全同理每个顶点存储对应区间的 GCD或 LCM合并即对两个孩子求 GCD/LCM。统计区间零的个数并查找第 k 个零把t[]改存每段中零的个数build、update、count_zero 直接用求和问题的思路实现即可解决统计部分。查找第 k 个零时从根下降看左孩子存有的零的个数若 ≥ k 则进左孩子否则进右孩子并把 k 减去左孩子零的个数若整个数组零的个数不足 k返回 -1 作为特判int find_kth(int v, int tl, int tr, int k) { if (k t[v]) return -1; if (tl tr) return tl; int tm (tl tr) / 2; if (t[v*2] k) return find_kth(v*2, tl, tm, k); else return find_kth(v*21, tm1, tr, k - t[v*2]); }对应实测见 test/test_segment_tree.cpptest_section_kth_zero在zeros {0,1,1,0,0,1,0,1,0,1}上依次断言第 1、2、3、4、5 个零的位置为 1、2、5、7、9第 6 个返回 -1更新位置 4 后位置序列随之变化。查找前缀和达到给定值的第一个位置问题给定 x找最小的下标 i 使前缀和 $\sum_{j0}^{i-1} a[j] \ge x$假设数组元素非负。用二分前缀和查询是 O(log² n)更优做法是沿用上一节的下降思路依据左孩子的前缀和决定走向O(log n) 得到答案。查找区间内第一个大于 x 的元素问题在 $a[l \dots r]$ 中找最小的 i 使 $a[i] x$。二分max 前缀查询是 O(log² n)下降遍历可优化到 O(log n)int get_first(int v, int tl, int tr, int l, int r, int x) { if(tl r || tr l) return -1; if(t[v] x) return -1; if (tl tr) return tl; int tm tl (tr-tl)/2; int left get_first(2*v, tl, tm, l, r, x); if(left ! -1) return left; return get_first(2*v1, tm1, tr, l ,r, x); }求最大和子段查询给定区间 $a[l \dots r]$ 内使 $l \le l$、$r \le r$ 且元素和最大的子段 $a[l \dots r]$同时支持单点修改。数组元素可为负最优子段允许为空如全为负时答案为 0。这是线段树的非平凡用法每个顶点存四个值——段和、最大前缀和、最大后缀和、段内最大子段和。合并规则为当前顶点答案取三者最大值——左孩子答案最优子段完全在左段、右孩子答案完全在右段、左孩子最大后缀和 右孩子最大前缀和子段横跨两个孩子前缀/后缀和的计算则更简单struct data { int sum, pref, suff, ans; }; data combine(data l, data r) { data res; res.sum l.sum r.sum; res.pref max(l.pref, l.sum r.pref); res.suff max(r.suff, r.sum l.suff); res.ans max(max(l.ans, r.ans), l.suff r.pref); return res; }叶子初始化用make_data(val)sum valpref suff ans max(0, val)max(0,...) 实现允许空子段。build 与 update 与前述结构完全一致只是叶子调用make_data、父节点调用combinedata make_data(int val) { data res; res.sum val; res.pref res.suff res.ans max(0, val); return res; } void build(int a[], int v, int tl, int tr) { if (tl tr) { t[v] make_data(a[tl]); } else { int tm (tl tr) / 2; build(a, v*2, tl, tm); build(a, v*21, tm1, tr); t[v] combine(t[v*2], t[v*21]); } } void update(int v, int tl, int tr, int pos, int new_val) { if (tl tr) { t[v] make_data(new_val); } else { int tm (tl tr) / 2; if (pos tm) update(v*2, tl, tm, pos, new_val); else update(v*21, tm1, tr, pos, new_val); t[v] combine(t[v*2], t[v*21]); } }查询与简单线段树相同只是用combine代替求和/取最大data query(int v, int tl, int tr, int l, int r) { if (l r) return make_data(0); if (l tl r tr) return t[v]; int tm (tl tr) / 2; return combine(query(v*2, tl, tm, l, min(r, tm)), query(v*21, tm1, tr, max(l, tm1), r)); }对应实测见 test/test_segment_tree.cpptest_section_maximal_subsegment数组a {5, 8, -5, 6, 2, 3, -2, -5, 7, 6}整体最大子段和为 25把位置 2 更新为 -10 后区间[1,3]的最大子段和由 9 变为 8 等。在每个顶点保存整个子数组与前述压缩存储和、最小值等不同这一变体在每个顶点存储对应区间的全部元素根存整个数组、左孩子存前半段、右孩子存后半段。最简单的应用是按排序顺序存储更复杂的版本改用 set、map 等高级结构。每个顶点需要与区间长度成正比的内存直觉上像 O(n²)但完整树只需O(n log n)——因为每个数组元素恰好落入 O(log n) 个段树高为 O(log n)。这类结构常与 2D 数据结构类比本质上是一种能力受限的二维结构。无修改查询区间内第一个 ≥ x 的数Merge Sort Tree对三元组查询 $(l, r, x)$求 $a[l \dots r]$ 中最小的大于等于 x 的数。每个顶点存对应区间的有序列表构建即自底向上合并两个孩子的有序列表双指针线性时间STL 的merge已内置该算法。由于结构与归并排序极其相似这种数据结构常被称为归并排序树Merge Sort Treevectorint t[4*MAXN]; void build(int a[], int v, int tl, int tr) { if (tl tr) { t[v] vectorint(1, a[tl]); } else { int tm (tl tr) / 2; build(a, v*2, tl, tm); build(a, v*21, tm1, tr); merge(t[v*2].begin(), t[v*2].end(), t[v*21].begin(), t[v*21].end(), back_inserter(t[v])); } }内存 O(n log n)、构建 O(n log n)每个列表按自身规模线性构建。查询把区间拆成 O(log n) 个与树节点重合的子段每个子段内对有序列表二分查找lower_bound答案取各子段结果的最小值故单次查询O(log² n)int query(int v, int tl, int tr, int l, int r, int x) { if (l r) return INF; if (l tl r tr) { vectorint::iterator pos lower_bound(t[v].begin(), t[v].end(), x); if (pos ! t[v].end()) return *pos; return INF; } int tm (tl tr) / 2; return min(query(v*2, tl, tm, l, min(r, tm), x), query(v*21, tm1, tr, max(l, tm1), r, x)); }其中INF为大于数组中所有数的大常量语义是该区间内不存在 ≥ x 的数。对应实测见 test/test_segment_tree.cpptest_section_smallest_number_greater_or_equal如对区间[2,4]元素{-5, 6, 2}查询 ≥ -10 得 -5、≥ -4 得 2、≥ 3 得 6、≥ 7 返回 INF。带修改查询区间内第一个 ≥ x 的数上一方案无法在查询间修改数组。若支持赋值 $a[i] y$则把每个顶点的有序列表换成支持快速查找、删除、插入的平衡结构因数组可能含重复值最优选择是multiset。构建方式同上但合并 multiset构建时间 O(n log² n)C STL 未保证红黑树可线性合并。查询改为调用 multiset 的lower_bound成员函数std::lower_bound只对随机访问迭代器保证 O(log n)。修改请求沿树下降删除旧值的一个出现并插入新值void update(int v, int tl, int tr, int pos, int new_val) { t[v].erase(t[v].find(a[pos])); t[v].insert(new_val); if (tl ! tr) { int tm (tl tr) / 2; if (pos tm) update(v*2, tl, tm, pos, new_val); else update(v*21, tm1, tr, pos, new_val); } else { a[pos] new_val; } }该修改查询同样为 O(log² n)。用 Fractional Cascading 加速到 O(log n)目标是同一问题但查询 O(log n)。fractional cascading分数级联是一种把同时进行的多次二分合并为一次的技术。朴素做法是把 k 个有序列表合并成一个大列表并记录每个元素在各列表中的搜索结果需要 O(n·k) 内存分数级联通过每个新列表包含原列表再加其后一个新列表的每第二个元素把内存降到 O(n)只需存两个索引即可用一次二分回答。对线段树的应用顶点保存左右子树元素合并后的有序列表同 Merge Sort Tree并对每个元素额外记录两个位置——左孩子列表中第一个 ≥ y 的索引 i右孩子列表中第一个 ≥ y 的索引 j这两个值可在构建合并时一并算出。查询时只需在根做一次二分拿到 $y \ge x$ 的最小元素及其两个索引之后每到一个节点用 O(1) 查找继续直到覆盖查询区间。总复杂度 O(log n)根节点一次二分 其余节点常数工作代价是内存为普通 Merge Sort Tree 的 3 倍。该技巧天然适用于无修改问题支持修改需要把有序数组换成multiset、索引换成迭代器并小心维护。其他可能的变体每个顶点除了存 vector/multiset还可以存其他数据结构嵌套线段树见下文高维推广、Fenwick 树、笛卡尔树等由此衍生出整整一类新应用。区间更新Lazy Propagation前述所有修改都只影响单个元素线段树还能以同样 O(log n) 处理整个连续区间的修改。区间加、单点查询修改查询把区间 $a[l \dots r]$ 每个元素加上 x查询只需返回 $a[i]$ 当前值。为高效处理加操作在每个顶点记录应加到对应区段所有元素上的值例如给整个数组加 3只需把 3 放到根一般地把查询区间划分为若干树节点子段每个子段只改 O(log n) 个顶点。查询某元素时沿树下行把沿途所有值累加void build(int a[], int v, int tl, int tr) { if (tl tr) { t[v] a[tl]; } else { int tm (tl tr) / 2; build(a, v*2, tl, tm); build(a, v*21, tm1, tr); t[v] 0; } } void update(int v, int tl, int tr, int l, int r, int add) { if (l r) return; if (l tl r tr) { t[v] add; } else { int tm (tl tr) / 2; update(v*2, tl, tm, l, min(r, tm), add); update(v*21, tm1, tr, max(l, tm1), r, add); } } int get(int v, int tl, int tr, int pos) { if (tl tr) return t[v]; int tm (tl tr) / 2; if (pos tm) return t[v] get(v*2, tl, tm, pos); else return t[v] get(v*21, tm1, tr, pos); }区间赋值、单点查询修改查询把 $a[l \dots r]$ 全部赋为 p。每个顶点需要标记对应区段是否完全被同一个值覆盖。这样可实现惰性更新只改部分顶点其余不动被标记的顶点表示其区段所有元素都等于该值且整个子树应只含此值。例如给整个数组赋值只在根放一个值并打标记。当后续修改需要用到某个被标记顶点的子树时须先把根的信息下推到两个孩子再继续。总结任何查询修改或读取沿树下降前都应把当前顶点的信息推送给两个孩子叶子无需下推保证只应用必要的延迟修改复杂度不劣化为 O(log n)。实现需要push函数void push(int v) { if (marked[v]) { t[v*2] t[v*21] t[v]; marked[v*2] marked[v*21] true; marked[v] false; } } void update(int v, int tl, int tr, int l, int r, int new_val) { if (l r) return; if (l tl tr r) { t[v] new_val; marked[v] true; } else { push(v); int tm (tl tr) / 2; update(v*2, tl, tm, l, min(r, tm), new_val); update(v*21, tm1, tr, max(l, tm1), r, new_val); } } int get(int v, int tl, int tr, int pos) { if (tl tr) { return t[v]; } push(v); int tm (tl tr) / 2; if (pos tm) return get(v*2, tl, tm, pos); else return get(v*21, tm1, tr, pos); }注意get也可换一种写法不做延迟下推而是一旦marked[v]为真就直接返回t[v]。区间加、区间最大值查询修改给区间内所有元素加一个数查询求区间最大值。每个顶点存对应子段的最大值另外每个顶点还要存尚未传播给孩子的加数。进入孩子前调用push把值传给两个孩子update与query都需要在递归前 pushvoid build(int a[], int v, int tl, int tr) { if (tl tr) { t[v] a[tl]; } else { int tm (tl tr) / 2; build(a, v*2, tl, tm); build(a, v*21, tm1, tr); t[v] max(t[v*2], t[v*2 1]); } } void push(int v) { t[v*2] lazy[v]; lazy[v*2] lazy[v]; t[v*21] lazy[v]; lazy[v*21] lazy[v]; lazy[v] 0; } void update(int v, int tl, int tr, int l, int r, int addend) { if (l r) return; if (l tl tr r) { t[v] addend; lazy[v] addend; } else { push(v); int tm (tl tr) / 2; update(v*2, tl, tm, l, min(r, tm), addend); update(v*21, tm1, tr, max(l, tm1), r, addend); t[v] max(t[v*2], t[v*21]); } } int query(int v, int tl, int tr, int l, int r) { if (l r) return -INF; if (l tl tr r) return t[v]; push(v); int tm (tl tr) / 2; return max(query(v*2, tl, tm, l, min(r, tm)), query(v*21, tm1, tr, max(l, tm1), r)); }推广到更高维度线段树可自然推广到多维二维情况下先按第一维索引建普通线段树再对每个段按第二维索引建普通线段树。简单二维线段树给定矩阵 $a[0 \dots n-1, 0 \dots m-1]$查询子矩阵 $a[x_1 \dots x_2, y_1 \dots y_2]$ 的和或最小/最大值并支持单点修改 $a[x][y] p$。构建分两个模块先沿 x 坐标建树build_x再在 x 的每个段上沿 y 建树build_y。build_y的叶子有两种情况x 段长度为 1 时直接取矩阵对应值x 段长度大于 1 时合并 x 方向上左右两个孩子的同 y 段值void build_y(int vx, int lx, int rx, int vy, int ly, int ry) { if (ly ry) { if (lx rx) t[vx][vy] a[lx][ly]; else t[vx][vy] t[vx*2][vy] t[vx*21][vy]; } else { int my (ly ry) / 2; build_y(vx, lx, rx, vy*2, ly, my); build_y(vx, lx, rx, vy*21, my1, ry); t[vx][vy] t[vx][vy*2] t[vx][vy*21]; } } void build_x(int vx, int lx, int rx) { if (lx ! rx) { int mx (lx rx) / 2; build_x(vx*2, lx, mx); build_x(vx*21, mx1, rx); } build_y(vx, lx, rx, 1, 0, m-1); }该结构仍用线性内存但常数更大16nm构建为线性时间。查询同样按先拆第一维、对每个到达的顶点调用对应第二维线段树的原则int sum_y(int vx, int vy, int tly, int try_, int ly, int ry) { if (ly ry) return 0; if (ly tly try_ ry) return t[vx][vy]; int tmy (tly try_) / 2; return sum_y(vx, vy*2, tly, tmy, ly, min(ry, tmy)) sum_y(vx, vy*21, tmy1, try_, max(ly, tmy1), ry); } int sum_x(int vx, int tlx, int trx, int lx, int rx, int ly, int ry) { if (lx rx) return 0; if (lx tlx trx rx) return sum_y(vx, 1, 0, m-1, ly, ry); int tmx (tlx trx) / 2; return sum_x(vx*2, tlx, tmx, lx, min(rx, tmx), ly, ry) sum_x(vx*21, tmx1, trx, max(lx, tmx1), rx, ly, ry); }复杂度O(log n log m)先沿第一维下降对每个经过的顶点再沿第二维查询一次。修改类似先下第一维、再下第二维void update_y(int vx, int lx, int rx, int vy, int ly, int ry, int x, int y, int new_val) { if (ly ry) { if (lx rx) t[vx][vy] new_val; else t[vx][vy] t[vx*2][vy] t[vx*21][vy]; } else { int my (ly ry) / 2; if (y my) update_y(vx, lx, rx, vy*2, ly, my, x, y, new_val); else update_y(vx, lx, rx, vy*21, my1, ry, x, y, new_val); t[vx][vy] t[vx][vy*2] t[vx][vy*21]; } } void update_x(int vx, int lx, int rx, int x, int y, int new_val) { if (lx ! rx) { int mx (lx rx) / 2; if (x mx) update_x(vx*2, lx, mx, x, y, new_val); else update_x(vx*21, mx1, rx, x, y, new_val); } update_y(vx, lx, rx, 1, 0, m-1, x, y, new_val); }压缩二维线段树若问题是平面上 n 个点 $(x_i, y_i)$查询统计落在矩形 $((x_1, y_1), (x_2, y_2))$ 内的点数则朴素二维线段树的 O(n²) 元素大多浪费——每个点只落入第一维的 O(log n) 个段第二维全部段的总有效规模为 O(n log n)。改进做法在第一维每个顶点上只用恰好落入该 x 区间的那些点的 y 坐标构建第二维线段树于是每棵第二维树占用恰如其分的内存总量降到O(n log n)查询仍为 O(log² n)第二维上做二分不劣化复杂度。代价是不支持修改新点出现需要在第二维树中间插入新元素无法高效完成。这种压缩结构本质上等价于每个顶点保存子数组的一维线段树变体即前文的 Merge Sort Tree 一类因此若二维线段树因无法修改而不适用可用更强大的嵌套结构如笛卡尔树替代内层线段树。保留历史版本持久化线段树持久化数据结构会为每次修改保留其先前状态允许访问任意历史版本并对其执行查询。线段树可以高效时间与内存兼优地持久化任意修改只改变从根到受影响叶子的 O(log n) 个顶点因此若用指针存储树每个顶点持左右孩子指针修改时只需新建被影响的顶点、其余顶点继续被旧版本复用单次修改创建 O(log n) 个新顶点并产生一个新根旧版本原封不动。求和与单点修改的持久化示例struct Vertex { Vertex *l, *r; int sum; Vertex(int val) : l(nullptr), r(nullptr), sum(val) {} Vertex(Vertex *l, Vertex *r) : l(l), r(r), sum(0) { if (l) sum l-sum; if (r) sum r-sum; } }; Vertex* build(int a[], int tl, int tr) { if (tl tr) return new Vertex(a[tl]); int tm (tl tr) / 2; return new Vertex(build(a, tl, tm), build(a, tm1, tr)); } int get_sum(Vertex* v, int tl, int tr, int l, int r) { if (l r) return 0; if (l tl tr r) return v-sum; int tm (tl tr) / 2; return get_sum(v-l, tl, tm, l, min(r, tm)) get_sum(v-r, tm1, tr, max(l, tm1), r); } Vertex* update(Vertex* v, int tl, int tr, int pos, int new_val) { if (tl tr) return new Vertex(new_val); int tm (tl tr) / 2; if (pos tm) return new Vertex(update(v-l, tl, tm, pos, new_val), v-r); else return new Vertex(v-l, update(v-r, tm1, tr, pos, new_val)); }每次修改获得一个新根把各版本根存入数组即可快速切换版本用对应根调用查询函数即作用于该版本。几乎任何线段树都可按此思路转为持久化结构。应用求区间内第 k 小的数查询区间 $a[l \dots r]$ 内第 k 小的元素用二分Merge Sort Tree 需要 O(log³ n)而持久化线段树只需O(log n)。先考虑简化版元素满足 $0 \le a[i] n$且只需查前缀。构造一棵数组直方图线段树叶子统计各值出现次数内部顶点统计区间内元素总数用持久化方式依次插入 $a[1], a[2], \dots, a[n]$记 $root_i$ 为插入前 i 个元素后的根其子树即前缀 $a[1 \dots i]$ 的直方图。利用查找第 k 个零同款下降技巧即可 O(log n) 定位第 k 小的元素。推广到任意区间 $a[l \dots r]$该区间的直方图恰为 $root_r$ 与 $root_{l-1}$ 之差——每个顶点用 $root_r$ 的计数减去 $root_{l-1}$ 的计数。实现时find_kth同时传入左右两个顶点指针Vertex* build(int tl, int tr) { if (tl tr) return new Vertex(0); int tm (tl tr) / 2; return new Vertex(build(tl, tm), build(tm1, tr)); } Vertex* update(Vertex* v, int tl, int tr, int pos) { if (tl tr) return new Vertex(v-sum1); int tm (tl tr) / 2; if (pos tm) return new Vertex(update(v-l, tl, tm, pos), v-r); else return new Vertex(v-l, update(v-r, tm1, tr, pos)); } int find_kth(Vertex* vl, Vertex *vr, int tl, int tr, int k) { if (tl tr) return tl; int tm (tl tr) / 2, left_count vr-l-sum - vl-l-sum; if (left_count k) return find_kth(vl-l, vr-l, tl, tm, k); return find_kth(vl-r, vr-r, tm1, tr, k-left_count); }构建时保存初始根与每次更新后的根int tl 0, tr MAX_VALUE 1; std::vectorVertex* roots; roots.push_back(build(tl, tr)); for (int i 0; i a.size(); i) { roots.push_back(update(roots.back(), tl, tr, a[i])); } // find the 5th smallest number from the subarray [a[2], a[3], ..., a[19]] int result find_kth(roots[2], roots[20], tl, tr, 5);对元素取值无界的数组通过索引压缩即可归约到上述模型把最小元素映射为 0、次小映射为 1……用map之类结构在 O(log n) 时间双向转换值与其索引。该实现的实测见 test/test_segment_tree.cpptest_kth_smallest_persistent对 20 个元素、MAX_VALUE 100的数组依次断言整体第 1/2/3/20 小为 3/11/13/98区间[9,15]索引 9 到 15第 16 小为 48/66/72/72/89/98。动态隐式/稀疏线段树当数组规模巨大如 $n \approx 10^9$且初始值都是某个默认元素、无法预先完整建树时可以惰性增量建树只创建根其他顶点按需创建。指针实现下进入孩子前先检查其是否存在不存在则创建。每类查询仍为 O(log n)例如 $\log_2 10^9 \approx 30$足够小。下面实现支持位置加值初始全 0与区间求和两种操作Vertex(0, n)为隐式树根struct Vertex { int left, right; int sum 0; Vertex *left_child nullptr, *right_child nullptr; Vertex(int lb, int rb) { left lb; right rb; } void extend() { if (!left_child left 1 right) { int t (left right) / 2; left_child new Vertex(left, t); right_child new Vertex(t, right); } } void add(int k, int x) { extend(); sum x; if (left_child) { if (k left_child-right) left_child-add(k, x); else right_child-add(k, x); } } int get_sum(int lq, int rq) { if (lq left right rq) return sum; if (max(left, lq) min(right, rq)) return 0; extend(); return left_child-get_sum(lq, rq) right_child-get_sum(lq, rq); } };该思路可向多种方向扩展例如结合 Lazy Propagation 支持区间更新。仓库中的配套测试与运行方式本文所有可运行代码均以{.cpp file...}形式内嵌于 src/data_structures/segment_tree.md。仓库的测试流水线是这样闭环的test/extract_snippets.py 扫描src/下所有.md用正则^\s*\{.cpp\sfile(\S)\}$提取带file标注的代码块生成为同名.h头文件test/test_segment_tree.cpp 通过#include xxx.h把这些片段纳入六个命名空间Implementation、MaximumAndCount、KthZero、MaximalSubsegment、SmallestGreaterOrEqual、KthSmallest用assert对每个算法变体做正确性验证test/test.sh 先运行提取脚本再用g -stdc17 -fsanitizeundefined -fno-sanitize-recover编译并逐个执行各.cpp测试全部通过即视为成功。在 src/navigation.md 中Segment Tree 被编排在 Data Structures → Trees 分组下与 Disjoint Set Union、Fenwick Tree、Sqrt Decomposition、Treap、Sqrt Tree 等并列是仓库算法体系中的核心数据结构之一。小结线段树用一个线性内存的二叉树把区间信息组织得层次分明构建 O(n)区间查询与单点/区间修改均为 O(log n)。从最简求和查询出发通过更换节点存储内容与合并操作可以衍生出最大值及其计数、GCD/LCM、第 k 个零、最大和子段等丰富的查询变体在顶点保存整个子数组则得到 Merge Sort Tree 并可结合 Fractional Cascading 进一步加速配合 Lazy Propagation 可支持整段区间更新沿两个坐标嵌套可推广为二维线段树基于指针复用又可获得持久化与动态隐式线段树。这套循序渐进的方法论正是 cp-algorithms 希望传达的通用建模能力——几乎所有区间查询 点/区间修改的问题都能在其中找到对应的组合方式。练习题目以下为文档原文附带的练习资源均来自外部评测平台可按需练习SPOJ – KQUERY持久化线段树 / 归并排序树Codeforces – Xenia and Bit OperationsUVA 11402 – Ahoy, Pirates!SPOJ – GSS3最大和子段Codeforces – Sereja And BracketsCodeforces – Distinct Characters QueriesCodeforces – Knight Tournament适合初学者Codeforces – Ant colonyCodeforces – Drazil and ParkCodeforces – Circular RMQCodeforces – Lucky ArrayCodeforces – The Child and SequenceCodeforces – DZY Loves Fibonacci NumbersLazy PropagationCodeforces – Alphabet PermutationsCodeforces – Eyes ClosedCodeforces – Kefa and WatchCodeforces – A Simple TaskCodeforces – SUM and REPLACECodeforces – XOR on SegmentLazy PropagationCodeforces – Please, another Queries on Array?Lazy PropagationCOCI – Deda最后一个 ≤ x 的元素 / 二分查找Codeforces – The Untended Antiquity2DCSES – Hotel QueriesCSES – Polynomial QueriesCSES – Range Updates and Sums赞分享文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载相关推荐Swift Package Manager 包注册表Package Registry指南包发布、搜索与下载的完整工作流Swift Package Manager 包注册表Package Registry指南包发布、搜索与下载的完整工作流 本文将带你掌握 Swift Pac开发工具构建工具30 分钟接入第一台摄像头WVP-GB28181-Pro 开源国标视频监控平台实战指南30 分钟接入第一台摄像头WVP GB28181 Pro 开源国标视频监控平台实战指南 WVP GB28181 Pro 是一个基于 GB28181 2016后端音视频前端如何创建Open Mercato Worker.worker.ts文件与并发控制指南如何创建Open Mercato Worker.worker.ts文件与并发控制指南 Open Mercato 是一款面向 CRM/ERP 与电商场景的开源上一篇Rerun RotationAxisAngle 组件详解绕轴 3D 旋转的数据模型、Arrow 编码与 SDK 用法下一篇Foundry forge lint 规则详解inconsistent-type-names 与整数类型命名一致性检查创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考