如何使用数学教材的手法教小朋友数据结构
minstdfx
·
2026-10-26 18:56:18
·
算法·理论
UPD: 最新力作 https://www.luogu.com.cn/article/q3usb3ep
教会小朋友数据结构的博客，到底应该是怎么样，oier 搞了这么多年也没搞清楚。可能 bourbaki 的思路比较好，搞了个新数学运动，可惜后来废弃了，，，
约定
本文以通常的集合论为基础。自然数、整数、有限序列、映射、笛卡尔积、全序、树、归纳法及有限递归定理视为已建立。记 \mathbf N=\{0,1,\ldots\} ，\mathbf N_{>0}=\mathbf N\setminus\{0\} 。所有树均为有限树；所有未特别限定的区间均为整数区间。
对于 l,r\in\mathbf Z ，置
[l,r]=\{i\in\mathbf Z:l\le i\le r\},\qquad [n]=[1,n].
当 l>r 时，[l,r]=\varnothing 。对非空有限集合 E ，|E| 表示其基数。符号 \sqcup 表示不交并。映射的复合采用 (f\circ g)(x)=f(g(x)) 的约定。
对 n\ge1 ，置
\lambda(n)=1+\lfloor\log_2n\rfloor.
一切渐近估计均在 n\to\infty 的意义下使用；以 \lambda(n) 写出的界同时适用于 n=1 。
计算约定。 除另有说明，采用字长 w=\Omega(\log(n+1)) 的随机存取机模型。一个地址、一个下标及本文微型表的一个编码均占 O(1) 个字；字上的加减、比较、位运算、移位和随机存取的代价为 O(1) 。每一个被声明为基本操作的代数运算及其操作数的存储代价亦为 O(1) 。若采用任意精度整数而不满足后一约定，本文的时间界只计代数操作次数，空间界只计代数元素个数；位复杂度须另行计算。
尤其在群值求和的各项时间界中，群运算、求逆以及已知整数长度与群元素的乘法 (p,c)\mapsto pc 按基本操作计；若具体群的表示不支持常数时间求整数倍，应在相应公式中计入该运算的实际代价。一般摘要的合并、标记复合及标记作用也须满足各定理明示的常数时间条件。机器实现须保证所用整数运算不溢出，或明确在指定的剩余类环中计算。
初始化、查询、修改的代价分别计量。声称某表示支持某种操作，意指存在下文所定义的实现及相应正确性证明，不含有关最优性的主张。
第一章 聚合与作用
§1 结合律
定义 1.1。 半群为配备结合二元运算 \cdot:S\times S\to S 的非空集合 S 。幺半群为配备单位元 e 的半群。群为每一元素均可逆的幺半群。交换群亦称阿贝尔群，并通常采用加法记号。
设 M 为幺半群。对有限有序族 a=(a_1,\ldots,a_n)\in M^n ，定义
\Pi_a(\varnothing)=e,\qquad
\Pi_a([l,r])=a_l\cdot a_{l+1}\cdots a_r\quad(1\le l\le r\le n).
\tag{1.1}
右式的括号按结合律省略，其因子的次序不得改变。
命题 1.2。 若 l\le k<r ，则
\Pi_a([l,r])=\Pi_a([l,k])\cdot\Pi_a([k+1,r]).
\tag{1.2}
更一般地，若 [l,r]=I_1\sqcup\cdots\sqcup I_s 且各 I_j 为按从左至右次序排列的非空区间，则
\Pi_a([l,r])=\Pi_a(I_1)\cdots\Pi_a(I_s).
\tag{1.3}
证明。 对因子个数应用结合律，再对 s 归纳。\square
定义 1.3。 幺半群 M 上的左商恢复映射为定义在
D=\{(x,x\cdot y):x,y\in M\}
上的映射 \delta:D\to M ，满足 \delta(x,x\cdot y)=y 。该映射存在当且仅当 M 满足左消去律；存在时唯一。其存在本身不蕴含其可在常数时间内求值。
证明。 若 x\cdot y=x\cdot z ，则应用 \delta 得 y=z 。反之，左消去律保证关系 (x,x\cdot y)\mapsto y 单值。\square
群中的恢复映射为 \delta(x,z)=x^{-1}\cdot z 。交换性并非此式的条件。
定义 1.4。 若半群 S 满足 x\cdot x=x ，则称其为幂等半群。
命题 1.5。 设 S 为幂等半群，a 为 S 中的有限有序族。若非空区间 I,J 满足
\min I\le\min J,\quad \max I\le\max J,\quad I\cap J\ne\varnothing,
则
\Pi_a(I)\cdot\Pi_a(J)=\Pi_a(I\cup J).
\tag{1.4}
证明。 必要时为 S 外加单位元；所得幺半群仍幂等。令 x,y,z 分别为 I\setminus J 、I\cap J 、J\setminus I 上按原次序取得的积，空族的积取所加单位元。由结合律及 y^2=y ，
(x\cdot y)\cdot(y\cdot z)=x\cdot(y\cdot y)\cdot z=x\cdot y\cdot z.
右式即所求。\square
注。 命题 1.5 不要求交换律。它也不允许任意改变区间的合并次序。
§2 摘要与标记
定义 1.6。 设 M 为幺半群，\operatorname{End}(M) 为保持运算及单位元的自映射所成的幺半群，其运算为复合。标记作用为幺半群 T 连同同态
\Phi:T\longrightarrow\operatorname{End}(M).
记 \Phi_t=\Phi(t) ，1_T 为 T 的单位元。于是
\Phi_{1_T}=\operatorname{id}_M,\qquad
\Phi_{t\circ s}=\Phi_t\circ\Phi_s,
\tag{1.5}
\Phi_t(x\cdot y)=\Phi_t(x)\cdot\Phi_t(y),\qquad \Phi_t(e)=e.
\tag{1.6}
标记的运算记为 \circ ，以规定先施加 s 、后施加 t 所得标记为 t\circ s 。
定义 1.7。 设 A 为元素集合，\eta:A\to M 为摘要映射。序列 a\in A^n 在区间 I 上的摘要为
\sigma_a(I)=\Pi_{\eta\circ a}(I).
若 T 亦作用于 A ，记该作用为 \alpha ，且
\eta(\alpha_t(x))=\Phi_t(\eta(x)),
\tag{1.7}
则称 \eta 与两作用相容。
命题 1.8。 在定义 1.7 的条件下，将区间 I 中每个元素 a_i 替换为 \alpha_t(a_i) 后，该区间的摘要为 \Phi_t(\sigma_a(I)) 。
证明。 将式 (1.7) 逐项代入，再对 |I| 归纳使用式 (1.6)。\square
例 1.9。 设 G 为阿贝尔群。置
M=G\times\mathbf N,
\qquad (x,p)\cdot(y,q)=(x+y,p+q),
\qquad e=(0,0).
取 \eta(x)=(x,1) 。对 c\in G ，定义
\Phi_c(x,p)=(x+pc,p).
\tag{1.8}
此处 pc 为 p 个 c 的和。由于
x+y+(p+q)c=(x+pc)+(y+qc),
式 (1.8) 给出加法幺半群 G 在 M 上的标记作用。其摘要同时包含和与长度。
例 1.10。 设 R 为含单位元的交换环，取 M=R\times\mathbf N ，运算同上。对于 (\alpha,\beta)\in R^2 ，置
\Phi_{\alpha,\beta}(x,p)=(\alpha x+p\beta,p).
\tag{1.9}
标记的复合为
(\alpha,\beta)\circ(\gamma,\delta)
=(\alpha\gamma,\alpha\delta+\beta).
\tag{1.10}
单位元为 (1,0) 。在元素上，(1,c) 表示加 c ，(0,c) 表示赋值为 c 。例如在 R=\mathbf Z 中，先赋值为 0 后加 1 ，与先加 1 后赋值为 0 ，所得标记分别为 (0,1) 与 (0,0) 。故交换律并非一般标记作用的性质。
§3 表示的正确性
定义 1.11。 对固定的 n ，抽象状态空间为 \mathcal A=A^n 。一个表示由具体状态集合 \mathcal C 、合法状态子集 \mathcal V\subseteq\mathcal C 及解释映射 \rho:\mathcal V\to\mathcal A 组成。
设 U:\mathcal A\to\mathcal A 为修改，Q:\mathcal A\to Y 为查询。其实现分别为映射
\widehat U:\mathcal V\to\mathcal V,
\qquad \widehat Q:\mathcal V\to\mathcal V\times Y
并须满足
\rho\circ\widehat U=U\circ\rho,
\tag{1.11}
\widehat Q(c)=(c',y)\Longrightarrow
\rho(c')=\rho(c),\quad y=Q(\rho(c)).
\tag{1.12}
描述 \mathcal V 的等式及条件称为表示不变量。查询允许改变具体表示，但不得改变其解释。
本文中的区间查询为 a\mapsto\sigma_a([l,r]) ；单点赋值为 a_p\leftarrow x ；阿贝尔群上的区间加法为 a_i\leftarrow a_i+c ，i\in[l,r] 。区间和记为 \Sigma_a(I) 。
第二章 前缀与有限分割
§1 前缀表示
定义 2.1。 对 a\in M^n ，其前缀族为
P_0=e,\qquad P_i=P_{i-1}\cdot a_i\quad(1\le i\le n).
\tag{2.1}
命题 2.2。 若 M 具有左商恢复映射 \delta ，则
\Pi_a([l,r])=\delta(P_{l-1},P_r).
\tag{2.2}
特别地，对群有
\Pi_a([l,r])=P_{l-1}^{-1}\cdot P_r;
\tag{2.3}
对阿贝尔群有 \Sigma_a([l,r])=P_r-P_{l-1} 。
证明。 由命题 1.2，P_r=P_{l-1}\cdot\Pi_a([l,r]) ；应用定义 1.3。\square
推论 2.3。 若积及 \delta 的求值代价为 O(1) ，则前缀族的构造耗时 O(n) 、占用空间 O(n) ，每次非空区间查询耗时 O(1) 。
直接逐项聚合的最坏查询代价为 O(n) ；q 次此类查询的最坏代价为 O(qn) 。前缀表示将该总界改为 O(n+q) 。
命题 2.4。 对显式存储的阿贝尔群前缀和，单点增加 c 于位置 p 的更新公式为
P_i'=
\begin{cases}
P_i,&i<p,\\
P_i+c,&i\ge p.
\end{cases}
\tag{2.4}
因此该显式表示可在 O(n-p+1) 时间更新。对于 G=\mathbf Z 、c\ne0 ，若每个 P_i 均须以当前值单独存储，则必须改写 n-p+1 个不同单元。
证明。 分别计算前缀是否包含 p ；在所述整数情形，每个包含 p 的前缀和均改变。\square
§2 块内前缀
固定整数 B ，1\le B\le n ，置 m=\lceil n/B\rceil ，并定义有序分割
K_j=[(j-1)B+1,\min(jB,n)]\quad(1\le j\le m).
\tag{2.5}
引理 2.5。 任一区间 I\subseteq[n] 至多与两个块发生非空而不等于整块的相交；其余非空相交均为整块。
证明。 若块不包含 I 的任一端点而与 I 相交，则该块的两端点均位于 I 内，故该块包含于 I 。\square
构造 2.6。 设 G 为阿贝尔群。在各 K_j 中存储相对于该块左端点的全部前缀和，并存储原元素。整块之和为该块最后一个前缀和。对查询区间，按引理 2.5 分割；整块直接取和，其余至多两个片段用块内前缀相减。
命题 2.7。 构造 2.6 的初始化时间与空间均为 O(n) ；区间查询时间为 O(\lceil n/B\rceil) ；单点赋值或单点增加时间为 O(B) 。
证明。 查询至多读取 m 个整块和及四个块内前缀。修改仅影响所在块中从修改位置起的前缀，其个数不超过 B 。赋值先由旧元素求出增量。\square
推论 2.8。 若同时要求上述两种操作有同一个最坏上界，取 B=\lceil\sqrt n\rceil 可得 O(\sqrt n) 。
若已知查询次数 q 与修改次数 u ，则该表示的总上界为
O\!\left(n+q\left\lceil\frac nB\right\rceil+uB\right).
\tag{2.6}
因而 B\asymp\sqrt n 的选择以两种操作受相同比重约束为前提；它不是所有操作分布下的统一最优选择。
§3 平移表示
构造 2.9。 设 G 为阿贝尔群。具体状态取 (b,T)\in G^n\times G ，解释为
a_i=b_i+T.
\tag{2.7}
则
\Sigma_a([l,r])=\Sigma_b([l,r])+(r-l+1)T.
\tag{2.8}
全体元素增加 c 由 T\leftarrow T+c 实现；位置 p 赋值为 x 由 b_p\leftarrow x-T 实现。
证明。 将式 (2.7) 代入区间和并用交换律重排。两修改式直接满足定义 1.11。\square
§4 具有块标记的表示
构造 2.10。 对式 (2.5) 的每一块，存储 T_j\in G ；对每个位置存储 b_i\in G ；再存储
S_j=\sum_{i\in K_j}b_i.
\tag{2.9}
解释为
a_i=b_i+T_j\quad(i\in K_j).
\tag{2.10}
其区间查询按以下规则在各非空交集 J=I\cap K_j 上求和：
Q_j(J)=
\begin{cases}
S_j+|K_j|T_j,&J=K_j,\\
\displaystyle\sum_{i\in J}(b_i+T_j),&J\ne K_j.
\end{cases}
\tag{2.11}
区间 I 增加 c 时，对每个这样的 J 施行
\begin{cases}
T_j\leftarrow T_j+c,&J=K_j,\\
b_i\leftarrow b_i+c\ (i\in J),\quad S_j\leftarrow S_j+|J|c,&J\ne K_j.
\end{cases}
\tag{2.12}
单点赋值 a_p\leftarrow x ，p\in K_j ，由
d=x-T_j-b_p,\qquad b_p\leftarrow b_p+d,\qquad S_j\leftarrow S_j+d
\tag{2.13}
实现。
命题 2.11。 式 (2.9) 是上述操作的表示不变量；式 (2.11) 返回正确的区间和；式 (2.12)、(2.13) 实现所声明的抽象修改。
证明。 对整块，式 (2.12) 不改变任何 b_i ，故保持式 (2.9)，并由式 (2.10) 使块内各值增加 c 。对非整块，S_j 的增量等于被修改的 b_i 的增量之和。式 (2.13) 同理。式 (2.11) 是式 (2.10) 的逐项求和。\square
命题 2.12。 此表示的初始化时间与空间均为 O(n) ；区间查询及区间增加的时间均为
O\!\left(\left\lceil\frac nB\right\rceil+B\right),
\tag{2.14}
单点赋值的时间为 O(1) 。取 B=\lceil\sqrt n\rceil ，式 (2.14) 为 O(\sqrt n) 。
证明。 引理 2.5 将非整块访问限制在至多 2B 个位置；整块至多 m 个。其余由构造直接计数。\square
第三章 二进区间的层叠族
§1 区间树
固定 n\ge1 ，置
k=\lceil\log_2n\rceil,\qquad N=2^k.
\tag{3.1}
于是 n\le N<2n ，包括 n=1 的情形。
定义 3.1。 对 0\le d\le k 、0\le j<2^d ，置
D_{d,j}=[j2^{k-d}+1,(j+1)2^{k-d}].
\tag{3.2}
族 \mathscr D=\{D_{d,j}\} 称为 [N] 的二进区间族。以 D_{0,0} 为根；D_{d,j} 的两个儿子按次序为 D_{d+1,2j} 、D_{d+1,2j+1} 。所得有根有序二叉树记为 \mathcal T_N 。
将节点 D_{d,j} 编号为 u=2^d+j 。则根编号为 1 ，非叶节点 u 的两个儿子编号为 2u,2u+1 ，位置 i 对应叶编号 N+i-1 。以 I_u 表示节点 u 的区间，以 u\preceq v 表示 u 为 v 的祖先，允许 u=v 。
命题 3.2。 对 I,J\in\mathscr D ，若 I\cap J\ne\varnothing ，则 I\subseteq J 或 J\subseteq I 。并且 I_v\subseteq I_u 当且仅当 u\preceq v 。
证明。 每一层为 [N] 的分割，后一层是前一层的逐块二等分。设 I 的层数不小于 J 的层数，则 I 包含于 J 所在层的唯一一个区间。若与 J 相交，该区间只能为 J 。祖先关系的结论由连续细分的定义得到。\square
§2 规范分解
定义 3.3。 对非空区间 Q\subseteq[N] ，置
\mathscr C(Q)=\{I\in\mathscr D:I\subseteq Q,
\ \nexists J\in\mathscr D\ (I\subsetneq J\subseteq Q)\}.
\tag{3.3}
称其为 Q 的规范分解。
定理 3.4。 \mathscr C(Q) 是 Q 的一个不交分割。它是以 \mathscr D 中元素分割 Q 的所有方式中，基数最小者，且这样的最小分割唯一。
证明。 对 i\in Q ，从单点 \{i\} 沿祖先链上升，在仍包含于 Q 的节点中有唯一最大的一个，故规范区间覆盖 Q 。由命题 3.2，两个相交的规范区间必有包含关系；由极大性，它们相等。因此它们不交。
设 \mathscr P\subseteq\mathscr D 是 Q 的另一不交分割。每个 J\in\mathscr P 包含于唯一的规范区间：存在性来自沿祖先链上升，唯一性来自规范区间两两不交。因此 \mathscr P 将每个规范区间进一步分割，且每个规范区间至少需要 \mathscr P 的一个成员。故 |\mathscr P|\ge|\mathscr C(Q)| 。等号成立时，每个规范区间恰由 \mathscr P 的一个成员覆盖，该成员必等于此规范区间。于是 \mathscr P=\mathscr C(Q) 。\square
引理 3.5。 在任一固定层，满足 I\cap Q\ne\varnothing 而 I\nsubseteq Q 的区间至多有两个。
证明。 同层区间两两不交。一个与 Q 相交而不包含于 Q 的区间，必包含 Q 的左端点或右端点；每个端点在该层仅属于一个区间。\square
命题 3.6。 在每个非根层，\mathscr C(Q) 至多有两个成员。因此
|\mathscr C(Q)|\le 2k+1.
\tag{3.4}
证明。 一个非根规范区间的父区间与 Q 相交而不包含于 Q 。根据引理 3.5，同层这样的父区间至多两个。每个父区间至多有一个儿子包含于 Q ，否则父区间本身包含于 Q 。于是每个非根层至多产生两个规范区间。根层至多一个。\square
§3 规范分解的递归求取
构造 3.7。 在节点 u 被调用时，要求 I_u\cap Q\ne\varnothing 。若 I_u\subseteq Q ，输出 u 并终止该次调用；否则，按从左至右的次序，对与 Q 相交的儿子递归调用。初始调用为根。
命题 3.8。 构造 3.7 恰输出 \mathscr C(Q) ，且访问节点数不超过 1+4k 。
证明。 输出条件为自身包含于 Q 而在此前未遇到包含于 Q 的祖先，等价于定义 3.3。
只有与 Q 相交而不包含于 Q 的节点才产生后续调用。每层这种节点至多两个，各有至多两个儿子，故除根外每层访问至多四个节点；共有 k 个非根层。\square
注。 式 (3.4) 只计输出节点；构造的时间界由命题 3.8 给出，不能仅从输出个数推出。
§4 幺半群表示
设 a\in M^n 。将其扩张为 \widetilde a\in M^N ，其中 \widetilde a_i=e ，n<i\le N 。
构造 3.9。 对每个节点存储 v_u\in M ，要求
v_u=\Pi_{\widetilde a}(I_u).
\tag{3.5}
等价地，叶值为对应元素，且每个非叶节点满足
v_u=v_{2u}\cdot v_{2u+1}.
\tag{3.6}
按节点高度递增的顺序应用式 (3.6)，称为构建。单点赋值先改变相应叶，再沿祖先链按式 (3.6) 重算。
对查询 Q\subseteq[n] ，依构造 3.7 求得按从左至右排序的节点 u_1,\ldots,u_s ，返回
v_{u_1}\cdots v_{u_s}.
\tag{3.7}
定理 3.10。 构造 3.9 满足表示正确性；构建时间与空间为 O(n) ，单点赋值及区间查询的时间为 O(\lambda(n)) 。
证明。 式 (3.5) 与式 (3.6) 的等价性由命题 1.2 及对树高的归纳得到。单点修改仅改变包含该点的区间，而这些区间恰为叶的祖先链。查询由定理 3.4 及命题 1.2 正确。
树有 2N-1<4n 个节点；祖先链有 k+1=O(\lambda(n)) 个节点；查询代价由命题 3.8 控制。\square
此表示称为线段树。其定义不要求 M 交换，查询中的次序因而是结构的一部分。
第四章 加法标记的保留表示
§1 状态空间
固定阿贝尔群 G 及初始族 a^{(0)}\in G^n 。按第三章扩张至长度 N ，并仍记为 a^{(0)} 。记
A_u=\sum_{i\in I_u}a_i^{(0)}.
定义 4.1。 具体状态为各节点上的二元族 (s_u,t_u)\in G^2 ，合法性条件为
s_u=A_u+\sum_{v:\,u\preceq v}|I_v|t_v.
\tag{4.1}
解释映射定义为
a_i=a_i^{(0)}+\sum_{u:\,i\in I_u}t_u.
\tag{4.2}
只允许对 [n] 内的区间修改，因而扩张位置始终为零。
命题 4.2。 对任一合法状态，令
h_u=\sum_{v:\,v\prec u}t_v,
其中 v\prec u 表示严格祖先，则
\Sigma_a(I_u)=s_u+|I_u|h_u.
\tag{4.3}
证明。 对式 (4.2) 在 I_u 上求和。由命题 3.2，一个与 I_u 相交的标记区间或为其祖先区间，或包含于 I_u 。严格祖先标记出现 |I_u| 次；位于 u 子树中的标记 t_v 出现 |I_v| 次。用交换律重排并应用式 (4.1)。\square
推论 4.3。 式 (4.1) 等价于以下局部等式：
s_u=
\begin{cases}
a_i^{(0)}+t_u,&I_u=\{i\},\\
s_{2u}+s_{2u+1}+|I_u|t_u,&u\text{ 非叶}.
\end{cases}
\tag{4.4}
初始化取 t_u=0 、s_u=A_u 。
§2 修改
构造 4.4。 定义递归状态变换 \mathcal U(u,J,c) ，其前提为 \varnothing\ne J\subseteq I_u 且 J 为区间：
置 s_u\leftarrow s_u+|J|c 。
若 J=I_u ，置 t_u\leftarrow t_u+c ，终止。
否则，按儿子次序，对各满足 J\cap I_v\ne\varnothing 的儿子 v ，施行 \mathcal U(v,J\cap I_v,c) 。
区间 Q 增加 c 由 \mathcal U(1,Q,c) 定义。
命题 4.5。 构造 4.4 保持式 (4.1)，并在解释映射下恰使 Q 中各元素增加 c 。
证明。 被增加的标记恰位于 \mathscr C(Q) 。由定理 3.4，每个 i\in Q 恰属于一个这样的区间，Q 外的点不属于任何这样的区间；故式 (4.2) 的变化正是所声明的修改。
若 u 被访问，位于其子树中的被标记规范区间不交且并为 Q\cap I_u ，所以式 (4.1) 右侧增加 |Q\cap I_u|c ，与步骤 1 相同。若 u 未被访问，则没有其子树内的标记被改变；某个严格祖先可能被标记，但该标记不出现在式 (4.1) 中。因此所有节点均保持合法性。\square
§3 查询
构造 4.6。 对 \varnothing\ne J\subseteq I_u 及 h\in G ，递归定义
\mathcal Q(u,J,h)=
\begin{cases}
s_u+|I_u|h,&J=I_u,\\[2mm]
\displaystyle\sum_{v\text{ 为 }u\text{ 的儿子},\ J\cap I_v\ne\varnothing}
\mathcal Q(v,J\cap I_v,h+t_u),&J\ne I_u.
\end{cases}
\tag{4.5}
区间查询返回 \mathcal Q(1,Q,0) 。
命题 4.7。 若传入的 h 等于 u 的严格祖先标记之和，则式 (4.5) 返回 \Sigma_a(J) 。
证明。 对节点高度归纳。全包含情形由命题 4.2 得出；其余情形中，儿子的严格祖先标记之和为 h+t_u 。使用归纳假设并对不交交集求和。\square
定理 4.8。 构造 4.4 与 4.6 给出初始化时间及空间为 O(n) 、区间增加及区间求和时间均为 O(\lambda(n)) 的表示。
证明。 两构造访问的节点均为构造 3.7 访问的节点，且每节点只需常数个基本操作。正确性由命题 4.5、4.7 得出。\square
注。 此处称为“标记保留”或“标记永久化”的性质是：查询不必将祖先标记移入后代。它不构成对历史状态的保存，也不声称可推广至任意标记作用。
第五章 一般标记作用的下传表示
§1 递归解释
采用定义 1.6、1.7 的数据 (A,M,T,\eta,\alpha,\Phi) 。为处理 N-n 个扩张位置，外加一个元素 \bot ，规定
\eta(\bot)=e,\qquad \alpha_t(\bot)=\bot.
\tag{5.1}
此后 \eta,\alpha 表示相应扩张。对序列逐项施加 \alpha_t 的映射记为 \alpha_t^* ，序列连接记为 \Vert 。
定义 5.1。 具体状态包含每个叶 u 的元素 b_u\in A\sqcup\{\bot\} 、每个非叶 u 的标记 t_u\in T ，以及所有节点的摘要 v_u\in M 。递归定义节点所表示的序列
F_u=
\begin{cases}
(b_u),&u\text{ 为叶},\\
\alpha_{t_u}^*(F_{2u}\Vert F_{2u+1}),&u\text{ 非叶}.
\end{cases}
\tag{5.2}
合法状态满足
v_u=
\begin{cases}
\eta(b_u),&u\text{ 为叶},\\
\Phi_{t_u}(v_{2u}\cdot v_{2u+1}),&u\text{ 非叶}.
\end{cases}
\tag{5.3}
前 n 个叶的元素属于 A ，其余叶的元素为 \bot 。解释映射为取 F_1 的前 n 项。
命题 5.2。 合法状态满足 v_u=\sigma(F_u) ，其中 \sigma 表示对整个节点序列求摘要。
证明。 对节点高度归纳，使用命题 1.8 及式 (5.3)。\square
§2 三种局部变换
定义 5.3。 节点上的施加变换 \operatorname{Apply}(u,t) 定义如下：
v_u\leftarrow\Phi_t(v_u);
\qquad
\begin{cases}
b_u\leftarrow\alpha_t(b_u),&u\text{ 为叶},\\
t_u\leftarrow t\circ t_u,&u\text{ 非叶}.
\end{cases}
\tag{5.4}
非叶节点上的下传变换 \operatorname{Push}(u) 定义为：先记 t=t_u ，依次施行
\operatorname{Apply}(2u,t),\qquad
\operatorname{Apply}(2u+1,t),\qquad
t_u\leftarrow1_T.
\tag{5.5}
节点的 v_u 在式 (5.5) 中保持不变。
当 t_u=1_T 时，回算变换 \operatorname{Pull}(u) 定义为
v_u\leftarrow v_{2u}\cdot v_{2u+1}.
\tag{5.6}
命题 5.4。 \operatorname{Apply}(u,t) 保持 u 子树内部的合法性，并将 F_u 替换为 \alpha_t^*(F_u) 。\operatorname{Push}(u) 保持整个表示的合法性及解释不变。
证明。 叶情形由式 (1.7) 得出。非叶施加变换满足
\Phi_t\bigl(\Phi_{t_u}(v_{2u}\cdot v_{2u+1})\bigr)
=\Phi_{t\circ t_u}(v_{2u}\cdot v_{2u+1}),
与新的标记相容；序列解释按相同的作用律变换。
对于下传，变换后父节点的序列为
\alpha_t^*(F_{2u})\Vert\alpha_t^*(F_{2u+1})
=\alpha_t^*(F_{2u}\Vert F_{2u+1}),
恰等于变换前的 F_u 。又由式 (1.6)，变换后的两个儿子摘要之积等于原 v_u ，故 t_u=1_T 后式 (5.3) 仍成立。父节点解释及摘要未变，因而其所有祖先的不变量亦未变。\square
注。 单独对一个有严格祖先的节点施行 \operatorname{Apply} ，未必保持祖先处的摘要等式；下列递归构造负责其祖先的回算。
§3 区间变换
构造 5.5。 对非空区间 J\subseteq I_u ，定义修改 \mathcal U_T(u,J,t) ：
若 J=I_u ，施行 \operatorname{Apply}(u,t) 后终止。
否则施行 \operatorname{Push}(u) ；对每个与 J 相交的儿子 v 施行 \mathcal U_T(v,J\cap I_v,t) ；最后施行 \operatorname{Pull}(u) 。
区间 Q 的抽象操作 a_i\leftarrow\alpha_t(a_i) 由 \mathcal U_T(1,Q,t) 实现。
构造 5.6。 区间查询 \mathcal Q_T(u,J) 由如下递归规定：若 J=I_u ，返回 v_u ；否则先施行 \operatorname{Push}(u) ，再按从左至右的次序求取与 J 相交的儿子查询值，并依该次序取积。
定理 5.7。 构造 5.5、5.6 满足定义 1.11。若摘要合并、标记复合、标记作用及叶元素作用均为常数时间操作，则初始化时间与空间为 O(n) ，每次区间修改或查询的时间为 O(\lambda(n)) 。
证明。 对节点高度归纳。全包含的修改由命题 5.4 正确。非全包含时，下传不改变 F_u ，并使 t_u=1_T ；故对子序列的修改可在两个儿子上独立实施。由归纳假设，各儿子的解释和摘要均正确；回算恢复式 (5.3)。全包含的查询由命题 5.2 正确；其余情形由下传保持解释不变及命题 1.2 得到。查询的下传可以改变具体状态，但符合式 (1.12)。
每个递归展开节点附带至多两次常数时间的儿子施加操作。递归节点数由命题 3.8 控制，因而总时间仍为 O(\lambda(n)) 。初始化取各 t_u=1_T ，自叶向根合并。\square
推论 5.8。 例 1.9 给出区间增加与区间求和的表示；例 1.10 给出区间仿射变换与区间求和的表示。两者均满足定理 5.7 的复杂度界，但后者必须采用式 (1.10) 所规定的复合次序。
注。 节点摘要已经包含该节点自身标记的作用。只有在访问其儿子的局部表示之前才需要下传；直接返回一个全包含节点的摘要无需下传。
§4 斐波那契摘要
定义 5.9。 整数族 (f_m)_{m\in\mathbf N} 由
f_0=0,\qquad f_1=1,\qquad f_{m+2}=f_{m+1}+f_m
\tag{5.7}
唯一确定。置
Q=\begin{pmatrix}1&1\\1&0\end{pmatrix},
\qquad z_m=\begin{pmatrix}f_{m+1}\\f_m\end{pmatrix}.
\tag{5.8}
命题 5.10。 对 m,c\in\mathbf N ，
z_m=Q^m\begin{pmatrix}1\\0\end{pmatrix},
\qquad z_{m+c}=Q^cz_m.
\tag{5.9}
证明。 式 (5.7) 等价于 z_{m+1}=Qz_m 。从 z_0=(1,0)^{\mathsf T} 归纳。\square
命题 5.11。 在 \mathbf R 中置 \varphi=(1+\sqrt5)/2 、\psi=(1-\sqrt5)/2 。则
f_m=\frac{\varphi^m-\psi^m}{\sqrt5}.
\tag{5.10}
证明。 \varphi,\psi 均满足 x^2=x+1 ，故右式满足式 (5.7) 的递推关系及两个初值。由有限递归的唯一性得出。\square
设元素族为 a\in\mathbf N^n ，其查询为 \sum_{i=l}^r f_{a_i} ，修改为区间内 a_i\leftarrow a_i+c ，其中 c\in\mathbf N 。
构造 5.12。 取摘要幺半群 (\mathbf Z^2,+,0) ，\eta(m)=z_m ，标记作用为
\Phi_c(v)=Q^cv.
\tag{5.11}
对有限族求和，所得摘要的第二分量为所需查询值。由于矩阵乘法对向量加法分配，式 (5.11) 满足定义 1.6。也可将所有整数映入任一固定的含单位元交换环，例如 \mathbf Z/m\mathbf Z ，以在该环中求值。
为仅以矩阵和向量实现此构造，可将元素状态集合取为 A'=\{z_m:m\in\mathbf N\} ，将标记幺半群取为 T'=\{Q^c:c\in\mathbf N\} ，摘要映射取包含映射，元素作用取矩阵乘向量。映射
\Psi:\mathbf N^n\longrightarrow(A')^n,
\qquad (a_i)\longmapsto(z_{a_i})
将指数平移变为逐项矩阵作用，并保持全部指定查询值，均由式 (5.9) 得出。因此可在向量状态上使用定义 1.11 的表示，无须从向量恢复原指数。在剩余类环中 \Psi 即使不单射，也不影响这些操作与查询的相容性。
命题 5.13。 构造 5.12 可由第五章的下传表示实现。若给定一次修改的矩阵 Q^c ，该修改及查询均使用 O(\lambda(n)) 次常数维矩阵、向量运算。
若 c 以二进制整数给出而未附矩阵，则二进制幂法另需 O(\lambda(c+1)) 次矩阵运算。故该次修改的总界为
O\bigl(\lambda(n)+\lambda(c+1)\bigr).
\tag{5.12}
未预处理幂时，以二进制幂法逐一生成初始向量，初始化所需代数操作次数为 O\!\left(n+\sum_{i=1}^n\lambda(a_i+1)\right) ；所生成的线段树占用 O(n) 个向量或矩阵单元。
若初始指数及所有修改增量均属于 [0,U] ，预先顺次计算 Q^0,\ldots,Q^U ，则初始化总时间为 O(n+U) 、额外幂表空间为 O(U) ，其后每次操作为 O(\lambda(n)) 。实现中可直接存储矩阵标记，其复合为矩阵乘法，因而不必显式保存累计指数。
证明。 二进制幂法按指数的二进制位逐位平方并乘入所需幂，所需操作数与位数成正比。其余由定理 5.7 及常数维数得出。\square
§5 一个失效的推广
命题 5.14。 对所有 c,d\in\mathbf N ，有
Q^cQ^d=Q^{c+d}=Q^dQ^c.
\tag{5.13}
因此斐波那契平移标记两两可交换。
证明。 由同一幺半群元素的幂的运算法则及整数加法交换律。\square
但第四章中“将子节点的局部摘要增量直接加至祖先摘要”的规则不能由式 (5.13) 推出。
反例 5.15。 取长度 2 的指数族 (0,0) 。两个叶的局部向量均为 z_0=(1,0)^{\mathsf T} ，根摘要为 (2,0)^{\mathsf T} 。对全区间增加 1 ，将根摘要改为 (2,2)^{\mathsf T} 并在根保留 Q ，不改变叶的局部向量。再仅对第一个位置增加 1 。
从未吸收根标记的叶摘要计算出的局部增量为
\Delta=Qz_0-z_0=(0,1)^{\mathsf T}.
若将此增量直接加至根，则得到 (2,3)^{\mathsf T} ；实际指数族为 (2,1) ，其摘要却为
z_2+z_1=(3,2)^{\mathsf T}.
根处所需增量为 Q\Delta=(1,0)^{\mathsf T} 。故失效来自局部摘要与祖先摘要所处作用状态不同，并非矩阵幂不交换。此反例只否定上述未经补偿的更新式，不否定其他可能的标记保留表示。
第六章 二进赋值与 Fenwick 表示
§1 保留区间的编号
定义 6.1。 对 i\in\mathbf N_{>0} ，令 \nu_2(i) 为使 2^{\nu_2(i)} 整除 i 的最大非负整数，并置
\ell(i)=2^{\nu_2(i)},\qquad R_i=[i-\ell(i)+1,i].
\tag{6.1}
在足以容纳 i 的二进制补码字上，\ell(i)=i\mathbin{\&}(-i) 。此为位表示的等式，不是定义的前提。
命题 6.2。 在 \mathcal T_N 中保留根及所有左儿子。将保留节点映至其区间的右端点，得到保留节点集合与 [N] 的双射；端点 i 的对应区间为 R_i 。
证明。 长度为 2^t 的二进区间形如
[q2^t+1,(q+1)2^t].
一个非根节点为左儿子，当且仅当 q 为偶数。此时其右端点为 (2h+1)2^t ，故右端点的二进赋值恰为 t ，区间恰等于 R_i 。反之，任取 i<N ，写作 i=(2h+1)2^t ，所得 R_i 正是一个左儿子区间。i=N 对应根。由右端点唯一决定 t 及区间，故为双射。\square
命题 6.3。 若 i<N ，则保留节点树中 i 的最近严格祖先的编号为
p(i)=i+\ell(i).
\tag{6.2}
此处保留节点树将相邻保留祖先连接，略去未保留的中间节点。
证明。 设 h=\ell(i) 。节点 R_i 为左儿子，其原树父区间为 [i-h+1,i+h] 。若该父节点为左儿子或根，则已保留。否则它为右儿子，向父亲上升不改变右端点；继续上升，直到首次到达左儿子或根，右端点一直为 i+h 。该节点恰为最近保留祖先。\square
推论 6.4。 对 1\le x<y\le N ，
R_x\cap R_y\in\{\varnothing,R_x\};
\tag{6.3}
若 p(x)\le N ，则 R_x\subsetneq R_{p(x)} ；若 x<y<p(x) ，则 R_x\cap R_y=\varnothing 。
证明。 第一式由命题 3.2 及右端点次序得出；其余由最近保留祖先的定义得出。\square
对于任意 n ，仅使用 R_1,\ldots,R_n ；当 p(i)>n 时，i 在此截取结构中无父节点。因此截取结构一般是森林，不必是一棵树。
§2 群值表示
设 G 为阿贝尔群。
定义 6.5。 序列 a\in G^n 的 Fenwick 表示为族 c\in G^n ，满足
c_i=\Sigma_a(R_i).
\tag{6.4}
引理 6.6。 包含位置 p 的全部 R_i ，恰为下列序列对应的区间：
i_0=p,\qquad i_{j+1}=i_j+\ell(i_j),
\tag{6.5}
直到下一项超过 n 为止。
证明。 所列节点是 p 的保留祖先链，故均包含 p 。反之，若 p\in R_i ，则 i\ge p ，且 R_i 与 R_p 相交。由式 (6.3)，R_p\subseteq R_i ，故 i 位于该祖先链。\square
构造 6.7。 单点增加 d 于位置 p 时，对式 (6.5) 中每个合法下标施行 c_{i_j}\leftarrow c_{i_j}+d 。
命题 6.8。 构造 6.7 保持式 (6.4)，并使用 O(\lambda(n)) 次操作。
证明。 被修改的表项恰为包含 p 的区间和，由引理 6.6 得正确性。写 i=(2h+1)2^t ，则
i+\ell(i)=(h+1)2^{t+1},
所以每一步的二进赋值严格增加。合法下标的赋值不超过 \lfloor\log_2n\rfloor ，故步数为 O(\lambda(n)) 。\square
§3 前缀分解
命题 6.9。 对 r\in[0,n] ，定义
r_0=r,\qquad r_{j+1}=r_j-\ell(r_j)\quad(r_j>0).
\tag{6.6}
设 r_s=0 为首次到达零的项，则
[1,r]=\bigsqcup_{j=0}^{s-1}R_{r_j},
\qquad
\Sigma_a([1,r])=\sum_{j=0}^{s-1}c_{r_j}.
\tag{6.7}
并且 s 等于 r 的二进制表示中 1 的个数。
证明。 由定义，R_{r_j}=[r_{j+1}+1,r_j] 。这些区间相邻而不交，直至覆盖整个前缀。减去最低非零二进位恰清除一个 1 ，故循环次数如述。\square
定理 6.10。 Fenwick 表示支持 O(\lambda(n)) 时间的前缀和、区间和及单点增加，占用空间 O(n) 。区间和由两前缀相减得到。若另存当前元素，单点赋值先转化为单点增加。
证明。 由命题 6.8、6.9 及命题 2.2。\square
§4 构建
构造 6.11。 初始化 c_i=a_i ；按 i=1,\ldots,n 的次序，若 p(i)\le n ，则施行
c_{p(i)}\leftarrow c_{p(i)}+c_i.
\tag{6.8}
命题 6.12。 构造 6.11 在 O(n) 时间内建立式 (6.4)。
证明。 在保留节点森林中，一个节点 i 的子树节点编号集合恰为 R_i ：编号 p 位于该子树，当且仅当 R_p\subseteq R_i ，由引理 6.6 等价于 p\in R_i 。又父编号严格大于子编号，故递增下标次序保证处理一个节点时，其所有后代的初始值已经经各自唯一父边累计至该节点。于是处理 i 时 c_i=\sum_{p\in R_i}a_p 。每个节点至多向父节点传递一次。\square
注。 本章的局部增量公式以交换群为假设。静态的非交换群前缀恢复公式 (2.3)，不能直接证明同一 Fenwick 增量更新式适用于非交换群。
第七章 幂等聚合的倍长表示
§1 倍长表
固定幂等半群 S 及 a\in S^n 。本章仅涉及静态序列。
定义 7.1。 倍长表为
H_{j,i}=\Pi_a([i,i+2^j-1]),
\tag{7.1}
其定义域为 j\in[0,\lfloor\log_2n\rfloor] 、i\in[1,n-2^j+1] 。该表亦称 Sparse Table，简称 ST 表。
命题 7.2。 倍长表由以下递推唯一确定：
H_{0,i}=a_i,
\qquad
H_{j,i}=H_{j-1,i}\cdot H_{j-1,i+2^{j-1}}\quad(j\ge1).
\tag{7.2}
证明。 长度 2^j 的区间为两个相邻长度 2^{j-1} 区间的不交并；应用命题 1.2。\square
定理 7.3。 对 Q=[l,r]\subseteq[n] ，令
d=\lfloor\log_2(r-l+1)\rfloor.
则
\Pi_a(Q)=H_{d,l}\cdot H_{d,r-2^d+1}.
\tag{7.3}
证明。 令 L=r-l+1 ，b=2^d ，则 b\le L<2b 。区间
I=[l,l+b-1],\qquad J=[r-b+1,r]
均包含于 Q ，左端点及右端点各按相同次序排列，且 I\cup J=Q 、I\cap J\ne\varnothing 。应用命题 1.5。该证明包含 I=J=Q 的情形。\square
推论 7.4。 倍长表示的预处理时间及空间为 O(n\lambda(n)) ，区间查询时间为 O(1) 。
证明。 表项数不超过 n\lambda(n) ，每一项由常数次操作得到。预先构造整数对数表
L_1=0,\qquad L_s=L_{\lfloor s/2\rfloor}+1\quad(2\le s\le n),
\tag{7.4}
则 L_s=\lfloor\log_2s\rfloor ，构造代价 O(n) 。式 (7.3) 只需常数次查表及一次半群运算。\square
§2 有序集上的最值
定义 7.5。 设 (X,\le) 为全序集，a\in X^n 。在 X\times[n] 上采用字典序。记
q_i=(a_i,i),\qquad
\operatorname{rmq}_a(l,r)
=\underset{i\in[l,r]}{\operatorname{argmin}}\ q_i.
\tag{7.5}
由于第二分量互异，最小位置唯一；它是最小值最左侧的出现位置。\operatorname{rmq}_a 返回位置，区间最小值为 a_{\operatorname{rmq}_a(l,r)} 。
命题 7.6。 在全序集上取二者较小者所定义的二元运算满足结合律、交换律及幂等律。因此式 (7.3) 适用于式 (7.5)。
证明。 两种括号次序均返回三个元素中的最小者，其余性质由全序的定义直接得到。\square
在对偶全序上得到最大值查询。非负整数的最大公因数、固定字长的按位与及按位或亦给出幂等半群，故可用倍长表示；这些实例不改变定理 7.3 的假设。
术语约定。 下文 RMQ 专指全序集上的区间最小位置查询。一般幂等半群上的区间聚合与 RMQ 区分使用。
第八章 相邻差为一的序列
§1 块的等价类型
定义 8.1。 对 m\ge1 ，称 h=(h_1,\ldots,h_m)\in\mathbf Z^m 为单位差序列，若
h_{i+1}-h_i\in\{-1,1\}\quad(1\le i<m).
\tag{8.1}
长度为 b 的两个整数序列 x,y 称为平移等价，若存在 c\in\mathbf Z 使 y_i=x_i+c ，i\in[b] 。
命题 8.2。 两个同长序列平移等价，当且仅当它们的相邻差序列相同。平移等价的序列在每个共同下标区间上具有相同的最左最小位置。
证明。 平移保持差分。反之，相同差分给出
y_i-x_i=y_1-x_1
对一切 i 成立。平移保持大小关系及相等关系，故也保持带下标决胜的最小位置。\square
定义 8.3。 长度 b 的单位差序列的类型为
\tau=(b,\varepsilon_1,\ldots,\varepsilon_{b-1}),
\qquad \varepsilon_i\in\{-1,1\}.
\tag{8.2}
该类型的规范代表 z^\tau 由
z_1^\tau=0,\qquad z_{i+1}^\tau=z_i^\tau+\varepsilon_i
\tag{8.3}
定义。长度 b 的类型数恰为 2^{b-1} 。类型与块首值共同唯一确定整个块。
§2 有限微型表
固定块长上界 B\ge1 。
构造 8.4。 对所有长度 1\le b\le B 的类型 \tau ，及 1\le s\le t\le b ，存储
\mu_\tau(s,t)
=\underset{p\in[s,t]}{\operatorname{argmin}}\ (z_p^\tau,p).
\tag{8.4}
对固定的 \tau,s ，按 t=s,s+1,\ldots,b 的次序求取各项：初项为 s ，其后比较上一最小位置与新位置 t ，相等时保留较小下标。
命题 8.5。 构造全部微型表所需时间与空间均为
O\!\left(\sum_{b=1}^B2^{b-1}b^2\right)
=O(2^BB^2).
\tag{8.5}
一个实际块 K=[L,L+b-1] 的类型为 \tau 时，子区间 [L+s-1,L+t-1] 的最左最小位置为
L+\mu_\tau(s,t)-1.
\tag{8.6}
证明。 每个类型先在 O(b) 时间生成规范代表，再以 O(b^2) 次比较得到全部条目。总和不超过 B^2\sum_{b=1}^B2^{b-1}<2^BB^2 。式 (8.6) 由命题 8.2 得出。\square
将 -1,+1 分别编码为 0,1 ，类型的差分部分可由 b-1 位整数表示。将长度作为编码的一部分，可区分所有尾块类型。
§3 块间表示
构造 8.6。 将 [m] 按长度 B 分为连续非空块 K_1,\ldots,K_s ，其中 s=\lceil m/B\rceil ，最后一块的长度允许小于 B 。记录各块类型，并令
p_j=\operatorname{rmq}_h(\min K_j,\max K_j),
\qquad v_j=(h_{p_j},p_j).
\tag{8.7}
各 p_j 由微型表求得。在序列 (v_j)_{j=1}^s 上建立第七章的倍长表示，比较采用字典序。
对 Q=[l,r] ，若两端点属于同一块，返回式 (8.6)。否则，以以下非空部分分割 Q ：包含 l 的块的后缀、严格位于两端块之间的全部块、包含 r 的块的前缀。第一及第三部分的最小位置由微型表求出，中间部分若非空则由块间倍长表求出。比较至多三个候选键 (h_p,p) ，返回最小者的位置。
命题 8.7。 构造 8.6 正确，预处理时间与空间均为
O\!\left(m+2^BB^2+
\left\lceil\frac mB\right\rceil
\lambda\!\left(\left\lceil\frac mB\right\rceil\right)\right),
\tag{8.8}
每次查询时间为 O(1) ，前提是一个类型编码及一次表访问为字级操作。
证明。 各候选位置分别是一个不交部分上的唯一字典序最小者；这些部分并为 Q ，故候选中的最小者为 Q 的最小者。扫描所有差分并形成块类型耗时 O(m) ；式 (8.5) 控制微型表；推论 7.4 控制块间表示。查询只使用有界次数的表访问及比较。\square
§4 线性界
定理 8.8。 单位差序列的 RMQ 存在预处理时间 O(m) 、空间 O(m) 、每次查询时间 O(1) 的表示。
证明。 取
B=\max\left(1,\left\lfloor\tfrac12\log_2m\right\rfloor\right).
\tag{8.9}
对 m\ge16 ，有 B=\Theta(\log m) ，从而
\left\lceil\frac mB\right\rceil
\lambda\!\left(\left\lceil\frac mB\right\rceil\right)
=O\!\left(\frac m{\log m}\log m\right)=O(m).
\tag{8.10}
又
2^BB^2\le\sqrt m\,\frac{(\log_2m)^2}{4}=O(m),
\tag{8.11}
因为 (\log_2m)^2/\sqrt m 在 m\ge16 上有界。有限个较小的 m 由扩大常数覆盖。类型编码至多用 B-1=O(\log m) 位，表的地址亦为 O(\log m) 位，满足计算约定。代入式 (8.8)。\square
注。 式 (8.11) 不将 \sqrt m\log^2m 视为与 m 同阶；这里只使用它是 O(m) 。所有微型表的生成费用已经计入预处理，并未假定存在免费外部查表设施。
第九章 有根树的欧拉表示
§1 祖先序
定义 9.1。 设 T 为非空有限有根树，顶点集为 V ，根为 o 。以 u\preceq_Tv 表示 u 位于从 o 至 v 的唯一简单路径上。顶点深度 d(v) 为该路径的边数。顶点 u 的子树 T_u 由满足 u\preceq_Tv 的顶点构成。
命题 9.2。 对 u,v\in V ，公共祖先集非空，且在 \preceq_T 下具有唯一最大元素。
证明。 根为公共祖先。u 的全部祖先在 \preceq_T 下构成有限全序链，公共祖先集为该链的非空子集，故具有唯一最大元素。\square
定义 9.3。 命题 9.2 中的最大元素记为 \operatorname{lca}_T(u,v) ，称为最近公共祖先。
为每个顶点的儿子任取并固定一个全序，得到有序有根树。该附加选择不改变祖先序或最近公共祖先。
§2 欧拉序列
定义 9.4。 对空树，置 E(\varnothing) 为空序列。若 u 的儿子按固定次序为 v_1,\ldots,v_s ，递归定义
E(T_u)=(u)\Vert E(T_{v_1})\Vert(u)
\Vert\cdots\Vert E(T_{v_s})\Vert(u).
\tag{9.1}
当 s=0 时，右式约定为 (u) 。记 E(T)=(e_1,\ldots,e_m) ，并定义
h_j=d(e_j),\qquad
f(v)=\min\{j:e_j=v\}.
\tag{9.2}
命题 9.5。 若 |V|=n ，则 m=2n-1 ；任意相邻两项 e_j,e_{j+1} 为树上相邻顶点，故 h_{j+1}-h_j\in\{-1,1\} 。E(T_u) 在 E(T) 中占据一个连续因子，该因子包含 u 子树内全部顶点的全部出现。
证明。 若子树大小为 n_1,\ldots,n_s ，由归纳假设及式 (9.1)，
|E(T_u)|=1+\sum_{i=1}^s\bigl((2n_i-1)+1\bigr)
=2\left(1+\sum_{i=1}^sn_i\right)-1.
序列中的每次跨越均为沿某一父子边下降或返回；在子树内部使用归纳假设即可。连续因子性质由递归连接式直接得到：对子树的展开全部完成后，才连接其后的父顶点及下一子树；子树外不存在该子树顶点的其他展开。\square
§3 最浅顶点
定理 9.6。 设 u,v\in V ，
L=\min(f(u),f(v)),\qquad R=\max(f(u),f(v)),
\qquad w=\operatorname{lca}_T(u,v).
则
\min_{j\in[L,R]}h_j=d(w),
\qquad
\{e_j:j\in[L,R],\ h_j=d(w)\}=\{w\}.
\tag{9.3}
证明。 u,v 均位于 T_w ，故其首次出现均在 E(T_w) 所占的连续因子内；由命题 9.5，两首次出现之间的全部项亦位于 T_w 。因此区间内所有深度均不小于 d(w) ，且 T_w 中深度等于 d(w) 的顶点只能是 w 。
须证 w 在所考察区间内出现。若 w=u 或 w=v ，则它已经出现在相应端点。否则 u,v 位于 w 的两个不同儿子子树中。交换 u,v 后可设 f(u)<f(v) 。式 (9.1) 在完成包含 u 的儿子子树后、进入包含 v 的儿子子树前至少连接一次 (w) ，故 w 在区间中出现。由此得式 (9.3)。\square
注。 式 (9.3) 声称取得最浅深度的顶点唯一，不声称取得最浅深度的序列位置唯一。同一顶点 w 可以在 [L,R] 内出现多次。
推论 9.7。 采用第七章的最左最小位置约定，有
\operatorname{lca}_T(u,v)
=e_{\operatorname{rmq}_h(L,R)}.
\tag{9.4}
定理 9.8。 对具有 n\ge1 个顶点的有根树，最近公共祖先查询存在预处理时间 O(n) 、空间 O(n) 、每次查询时间 O(1) 的表示。
证明。 用式 (9.1) 的递归遍历生成 E,h,f 。每条边恰下降及返回各一次，故时间与输出空间为 O(n) ；递归栈空间至多 O(n) 。由命题 9.5，h 为长度 2n-1 的单位差序列，故适用定理 8.8。最后按式 (9.4) 查询。\square
第十章 笛卡尔树与一般 RMQ
§1 有序树与堆序
固定全序集 X 及 a\in X^n ，并沿用 q_i=(a_i,i) 的字典序。由于位置互异，q_1,\ldots,q_n 两两不同。
定义 10.1。 对区间 [l,r]\subseteq[n] ，递归定义有序二叉树 C_a[l,r] ：若 l>r ，取空树；否则置
m=\underset{i\in[l,r]}{\operatorname{argmin}}\ q_i,
\tag{10.1}
以 m 为根，左、右子树分别为 C_a[l,m-1] 、C_a[m+1,r] 。记 C_a=C_a[1,n] ，称为 a 的最小笛卡尔树。
递归定义的适用性来自两个子区间均严格短于原区间。
命题 10.2。 树 C_a[l,r] 的中序序列为 (l,l+1,\ldots,r) 。每个非根顶点 v 及其父顶点 u 满足
q_u<q_v.
\tag{10.2}
每个子树的顶点下标集合为一个连续区间，其根的键为该区间的唯一最小键。
证明。 对区间长度归纳。左右子树的中序序列由归纳假设给出，在两者之间插入根 m 即得完整下标序列。根由式 (10.1) 取区间最小键，因键互异，它严格小于所有真后代的键。每个子树仍由同一递归式生成，故其余结论同时成立。\square
命题 10.3。 C_a 是顶点集为 [n] 、中序序列为 (1,\ldots,n) 且满足式 (10.2) 的唯一有序二叉树。
证明。 满足堆序的根沿每条路径严格小于所有其他顶点，故必须是全体键的唯一最小者。中序条件随后唯一规定左右子树的顶点集为该根下标之前及之后的两个区间。对二者归纳。存在性由定义 10.1 及命题 10.2 已得。\square
§2 查询的等价
定理 10.4。 对 1\le l\le r\le n ，
\operatorname{rmq}_a(l,r)=\operatorname{lca}_{C_a}(l,r).
\tag{10.3}
证明。 置 z=\operatorname{lca}_{C_a}(l,r) 。其子树的下标集为某个连续区间 [L_z,R_z] ，且包含 l,r ；因此也包含整个 [l,r] 。由命题 10.2，q_z 不大于 [l,r] 内任一键。
还须证 z\in[l,r] 。若 z=l 或 z=r ，结论成立。否则，l,r 必位于 z 的不同儿子子树中；不然该儿子将成为比 z 更深的公共祖先。由中序下标次序，l 在左子树，r 在右子树，从而 l<z<r 。于是 z 是 [l,r] 内唯一最小键的位置。\square
§3 右链
定义 10.5。 非空有序二叉树的右链为从根开始反复取右儿子直到右儿子为空所得到的顶点序列。其末项可以具有非空左子树。
命题 10.6。 若一棵树的中序序列为 (1,\ldots,s) ，则顶点 s 为右链末项。若该树又满足式 (10.2)，则右链上的键按从根至末项的次序严格递增。
证明。 中序最后访问的顶点通过从根反复取右儿子得到；若当前顶点没有右儿子，则其左子树在它之前已被访问。故末项为 s 。键的单调性由父子堆序逐边推出。\square
§4 栈构造
以 0 表示空指针。为每个 i\in[n] 初始化左、右指针 L_i=R_i=0 。一个栈为有限序列 S=(s_1,\ldots,s_t) ，其末项为栈顶；空栈允许存在。
构造 10.7。 初始栈为空，根指针为 0 。对 i=1,2,\ldots,n ，施行如下有限过程：
令 z=0 。
当栈非空且 q_{s_t}>q_i 时，置 z=s_t 并删除栈末项；重复此步骤。
置 L_i=z 。若栈非空，以其当前末项 p 为下标，置 R_p=i ；否则置根指针为 i 。
将 i 接于栈尾。R_i 保持为 0 。
未被上述规则赋值的指针保持不变。
定理 10.8。 在处理完位置 i 后，当前树为 C_a[1,i] ，且栈按从根至末项的次序恰列出该树的右链。
证明。 对 i 归纳。空树及 i=1 的情形直接满足结论。设结论对 i-1 成立。由命题 10.6，栈中键严格递增，故步骤 2 删除其一个终端子序列。
若未弹出节点，则 z=0 ，原栈末项没有右儿子；将 i 接为其右儿子即可。由于循环停止条件及键互异，原末项的键小于 q_i ，堆序保持。
若弹出了节点，则最终的 z 是被弹出部分中最接近根的节点。它及其整个子树构成原树中序序列的一个终端区间。若保留栈非空，其末项 p 原来以 z 为右儿子；若保留栈为空，则 z 原为根。步骤 3 将该整个子树置为 i 的左子树，并以 i 取代它在原树中的位置。
在后一情形，循环给出 q_i<q_z ；若存在保留的 p ，另有 q_p<q_i 。故新添的两条可能的边均满足堆序，其余边未变。移动的子树中序顺序保持，且新顶点 i 在其后、在全树的最右端，因此新树中序序列为 (1,\ldots,i) 。由命题 10.3，新树必为 C_a[1,i] 。
新右链恰为保留的原栈后接 i ；被移动的子树已成为左子树，其节点不再位于右链。步骤 4 恢复栈不变量。\square
命题 10.9。 构造 10.7 的总时间为 O(n) ，空间为 O(n) 。
证明。 每个下标入栈恰一次、出栈至多一次。成功的弹栈比较至多 n 次；每次外层迭代至多另有一次使循环终止的键比较。其余赋值每次迭代为常数个。因此总操作数为 O(n) 。树指针及栈各占 O(n) 空间。\square
§5 一般静态最小位置查询
定理 10.10。 在约定的计算模型下，对任意全序集中的长度 n\ge1 的有限序列，RMQ 存在预处理时间 O(n) 、空间 O(n) 、每次查询时间 O(1) 的表示。
证明。 依构造 10.7，在 O(n) 时间构造 C_a ；依第九章，在该树上建立最近公共祖先表示。由定理 10.4，查询 [l,r] 等价于查询树中顶点 l,r 的最近公共祖先，后者为常数时间。各部分空间及预处理时间均线性。\square
若 (E,h,f) 是 C_a 的欧拉表示，则上述查询可写为单个等式
\operatorname{rmq}_a(l,r)
=E_{\operatorname{rmq}_h(\min(f(l),f(r)),\,\max(f(l),f(r)))}.
\tag{10.4}
式 (10.4) 的内层查询由第八章实现，不依赖正在构造的一般 RMQ。故此构造不存在递归定义的循环依赖。
推论 10.11。 将全序替换为其对偶，得到相同界的静态区间最大位置查询。定理 10.10 本身不提供对任意幂等半群的相同线性预处理界，也不提供动态修改操作。