稀疏表、RMQ-LCA 与 Mo 队

• 倍增表 up[k][v] 的递推定义与构建过程
• 查询时"从大到小枚举 + 不越界才跳"的贪心正确性
• 预处理与单次查询的复杂度分析

倍增表 up[k][v] 表示节点 v 向上跳 2^k 步到达的祖先，构建时令 up[0][v]=parent[v]，并递推 up[k][v]=up[k-1][up[k-1][v]]，即"2^k 级祖先 = 2^(k-1) 级祖先再跳 2^(k-1) 步"，预处理复杂度 O(n log n)。查询 LCA(u,v) 分两步：先用二进制位分解把深度较大的节点跳到与另一个节点同深度，再从 k=⌊log n⌋ 向 0 从大到小枚举，只要 up[k][u]≠up[k][v] 就同时上跳，最后返回二者的父节点，单次查询 O(log n)。

从大到小跳的原因是二进制分解的贪心正确性：跳升量必须按 2 的幂从高到低组合，等价于对"深度差"做二进制分解；更重要的是以 up[k][u]≠up[k][v] 作为判据，若二者相等说明 2^k 步已经到达 LCA 之上或恰为共同祖先，此时跳过去会越过 LCA，必须减小步长试探，最终必然停在 LCA 正下方，返回父节点即答案。

核心是"一步代价 O(1)、步长按 2 的幂递减"的倍增思想，与二分求第 k 级祖先的二进制分解一脉相承；"从大到小 + 不越界才跳"保证每一步决策在已定高位的基础上最优，是正确性的关键，面试时需强调不能从小到大跳。

• 点差分与边差分的标记方式差异
• 自底向上累加还原覆盖次数
• 为什么差分能在 O(1) 标记、O(n) 还原

点差分统计"每个点被路径覆盖的次数"：对路径 u→v，令 cnt[u]++、cnt[v]++、cnt[lca]--、cnt[parent[lca]]--，然后按 DFS 后序把子节点的 cnt 累加到父节点，最终 cnt[x] 就是 x 被覆盖的次数。边差分把边权挂在深度较大的端点上：cnt[u]++、cnt[v]++、cnt[lca]-=2，累加后 cnt[x] 表示 x 与其父节点之间那条边被覆盖的次数。

正确性来自差分与子树累加的对偶关系：路径 u→v 的影响恰好等于四个（或三个）标记在"后序累加"过程中的传播结果——LCA 处减一次或两次是为了抵消两个端点的增量在 LCA 上方多余的传导。一次差分 O(1) 标记、一次 DFS O(n) 累加，配合倍增预处理后总复杂度 O(n log n)（求 LCA 部分），统计本身是 O(n)。

把"路径覆盖"这种 O(路径长度) 的修改摊到 O(1) 的标记上，再用后序累加还原，是"离线 + 增量"思想的经典应用；点差分与边差分的区别只在 LCA 处减法的次数（点差分在 lca 与 parent[lca] 各减一次，边差分在 lca 减两次），回答时需区分清楚。

• inlabel 位标记与 Euler 序编号的关系
• ascendant 重路径压缩表的结构
• 与倍增法在复杂度和常数上的对比

Schieber-Vishkin 算法把树拆成 micro 与 macro 两层处理：预处理阶段为每个节点计算 inlabel（基于叶子编号的位标记，编码了节点在"叶子区间"中的位置信息）与 ascendant 数组（每个 inlabel 对应的最高祖先，即重路径压缩表），预处理 O(n) 时间与空间。查询时利用 inlabel 的位运算（最高位/最低位提取与异或操作）在 O(1) 时间内确定 LCA，无需二分或倍增的 log 因子。

工程实现要点：先做一次 DFS 获得 Euler 序编号，用"叶子个数与编号"构造 inlabel；ascendant 只需为每个可能的 inlabel 保存一条压缩路径，查询归结为两次位运算与一次数组访问。相比倍增法它实现复杂、常数较大，但查询严格 O(1)，适合查询量极大（如作为 RMQ 模块的底层 LCA 求解器）的场景。

Schieber-Vishkin 属于"micro-macro 分解 + 重路径压缩"流派，用位标记把祖先关系编码进常数次位运算；理解它有助于区分"O(log n) 查询"与"O(1) 查询"两类 LCA 方案的取舍，面试答出 inlabel 与 ascendant 两个结构即算掌握。

• 稀疏表的倍增递推与预处理复杂度
• 可重叠覆盖的幂等性前提
• 用 lzcnt/clz 位运算 O(1) 求 k

稀疏表预处理 f[k][i] 表示从 i 开始长度为 2^k 的区间最值，递推 f[k][i]=min(f[k-1][i], f[k-1][i+2^(k-1)])，预处理 O(n log n)。查询 [l,r] 时取 k=⌊log2(r-l+1)⌋，答案为 min(f[k][l], f[k][r-2^k+1])——两个长度 2^k 的区间恰好完全覆盖 [l,r] 且允许重叠，故 O(1) 返回。

位运算向量索引推导：k 可用 31-clz(len)（x86 的 lzcnt 指令或 __builtin_clz）在常数时间求出，避免二分查找 log2；存储上按"长度优先"排布二维数组可提升缓存命中。局限性：只支持可重叠合并的幂等操作（min/max/gcd），不支持求和类聚合；且不支持单点修改，修改后需 O(n log n) 重建。

可重叠覆盖是稀疏表的"幂等性"要求——区间合并两次与合并一次结果相同才允许重叠，这是 min/max 类聚合与 sum 类聚合的分水岭；位运算求 log2 让查询真正 O(1)，面试时把"clz 求 k + 两段覆盖"讲清楚即可。

• 一般 RMQ 经笛卡尔树归约到 LCA
• LCA 经 Euler Tour 深度序列归约到 ±1 RMQ
• 两条归约均为 O(n) 构造的闭环

一般 RMQ 与 ±1 RMQ 通过两条归约等价：一般 RMQ → 笛卡尔树（以数组值建堆序、以下标建中序），区间 [l,r] 的最值节点恰是下标 l 与 r 的 LCA，于是 RMQ 变成 LCA；LCA → ±1 RMQ 用 Euler Tour：DFS 进出时记录节点与其深度，深度序列相邻差恰为 ±1，LCA 是欧拉序区间内深度最小的点，即 ±1 RMQ。两条归约都是 O(n) 构造，闭合后任意 RMQ 都可用 ±1 RMQ 的 O(1) 方案求解。

工程实现：Euler 序列长度 2n-1，对深度数组做 ±1 RMQ（Fischer-Heun 或分块）；查询 LCA(u,v) 取 u 首次出现与 v 首次出现之间的深度最小点。该等价链是"任意 RMQ 都能 O(1) 查询"的理论基础，也是后续块预处理方案（Fischer-Heun）的前提。

归约链 RMQ→LCA→±1 RMQ 说明问题难度等价，只需攻克最特殊情形；理解归约方向与各环节构造（笛卡尔树、Euler tour）是高级 RMQ 面试的核心，回答时应把两个方向的构造各讲一步。

• 块大小取 (log n)/2 使块形态数只有 O(√n) 种
• 按形态打表共享预计算
• 跨块用稀疏表、块间块内两级查询

Fischer-Heun 算法在 ±1 RMQ 上把数组切成大小 b=⌊(log n)/2⌋ 的块，块内差分序列只有 ±1 两种取值，故本质不同的块形态只有 2^b=O(√n) 种。于是对每种形态预计算"块内任意子区间最值"的表（O(√n·b²)），块间最值用稀疏表（O((n/b)·log(n/b))）。查询时同块直接查形态表，跨块合并"左块内 + 块间 + 右块内"三段，总 O(1)。

预处理总量为 O(n)：块数 n/b 与形态数 2^b 同阶，总成本 O(n/b·b² + (n/b)log(n/b))=O(n)。这达成"线性预处理 + O(1) 查询"的 ±1 RMQ 最优复杂度，其通用模板是"先分块、块内模式打表、块间套高层结构"（即 4-ary 一类的多路划分思路）。

核心技巧是模式压缩——把重复出现的局部结构归并为少数原型并共享预计算，避免对每个位置单独建表；块粒度取 (log n)/2 使块形态数不超过 √n 是关键平衡点，面试时点出"形态数 = 2^b = √n"即抓住本质。

• 三维指针 (l, r, t) 的维护与排序准则
• 块大小 n^(2/3) 时的总移动量推导
• 修改指针的向前应用与向后撤销

带修改 Mo 队把每个询问表示为三元组 (l, r, t)，t 是"当前已应用的第几个修改"，额外维护修改指针：右移指针时正向应用一次修改（用 swap 原值/新值），左移时反向撤销。排序按 (l/B, r/B, t) 三级：l 指针移动总量 O(q·B)，r 指针在同一 (l 块, r 块) 组合内单调、组合间跳变，总量 O(n·(n/B))；t 指针在每个 (l 块, r 块) 组合内单调，组合数 (n/B)²，每组合最多移动 n 次，总量 O(n·(n/B)²)。

令 l、r、t 三者的移动量平衡：qB = n²/B = n³/B²，取 B=n^(2/3)，总复杂度 O(n^(5/3))（n、q 同阶时）。相比普通 Mo 的 O(n√n) 多出 n^(1/6) 因子，这是"时间维度换正确性"的代价；实战中若修改数远小于查询数，也可考虑分块重构替代。

三维 Mo 把修改看作时间轴上的指针，排序按两维分块、第三维单调，是普通 Mo 的自然推广；复杂度推导的关键是写出三个指针各自的移动量再对 B 求平衡，面试时给出 B=n^(2/3) 与 O(n^(5/3)) 即完整。

• 用 std::set 维护同值连续区间
• split 的区间切分与 assign 的合并回收
• 随机数据下段数的期望负漂移

Chtholly Tree（ODT，珂朵莉树）用 std::set 维护若干"值相同的连续区间"节点 [l,r,val]，按 l 排序。split(pos) 找到包含 pos 的区间并切成 [l,pos-1] 与 [pos,r] 两段，返回 pos 所在段；assign(l,r,val) 先 split(r+1)、再 split(l) 得到边界迭代器，删除 [l,r] 内的所有区间并插入新段——这一合并使段数下降。区间加、第 k 小、区间幂和等操作都先 split 再遍历段处理，每段 O(1) 或 O(log n)。

期望复杂度 O(n log n)：在随机数据下，每次随机区间操作先把涉及的段切开（至多 +2 段），再把覆盖的整段删除合并，段数的期望净变化为负（E[Δs]≈-s/2+2），使段数维持在较低水平；对 CF 896C 这类"随机生成 + 高频区间赋值"的题面，赋值操作持续回收段，均摊下总操作次数 O(n log n)（高概率）。

ODT 的正确性不依赖随机——任何数据下结果都正确，复杂度保证依赖"区间赋值频繁 + 随机区间"的模型；面试必须讲清"先 split(r+1) 再 split(l)"的边界顺序与迭代器失效问题，这是最容易出错的地方。

• 欧拉序（进出各一次）的长度与编码
• 路径转区间的两种情形与 lca 特判
• 奇偶翻转维护路径贡献

树上 Mo 队把"树上路径查询"转化为"数组区间查询"：DFS 时每个节点入栈记 in[u]、出栈记 out[u]（总长 2n 的欧拉序）。对路径 u→v（in[u]≤in[v]）：若 u 是 v 的祖先，路径对应区间 [in[u], in[v]]；否则对应 [out[u], in[v]]，且 LCA 不在区间内需单独计入。扫描区间时用 vis 数组翻转每个点的出现奇偶，区间内出现奇数次的点恰好构成路径（LCA 额外处理），贡献在 O(1) 内增减。

块分割：对 2n 长度的欧拉序取块大小 B=√(2n)，按 (l/B, r) 排序，与普通 Mo 完全相同的排序与移动框架；子树查询可退化为 [in[x], out[x]] 的单区间，是树上 Mo 的退化情形。正确性依赖"进出序 + 奇偶抵消"：非路径节点在区间内出现偶数次被抵消，路径节点恰好出现一次。

欧拉序把"路径"编码成"区间 + 奇偶计数"，使树问题落入 Mo 队框架；关键边界是 LCA 是否在区间内（祖先情形）以及奇偶翻转的正确性，面试时把两种情形画出来讲最清晰。

• 奇偶（Zigzag）排序减少 r 指针移动
• 内联函数、数组化访问与分支消除
• 缓存局部性与编译器优化配合

Mo 队在大数据量下的瓶颈在指针移动与函数调用开销，常数优化集中在排序与访问模式：块大小按 n/√q 手动调参；排序用奇偶（Zigzag）分块——l 所在块为奇数时 r 升序、偶数时 r 降序，使 r 指针在块间折返移动而非每次从头归位，r 指针移动量近乎减半。此外把 add/del 写成内联函数、用数组取代 map/unordered_map、把区间端点存成数组避免重复寻址、对排序后的询问做指针增量更新，都能显著降常数。

寄存器与局部性：add/del 内部避免分支与函数调用，用指针而非下标访问数组，让热点数据保持在寄存器与 L1 缓存中；块内元素访问连续，配合 -O2 与预取指令（__builtin_prefetch）进一步降低访存延迟。经验上这些优化在 10^6 查询下可带来 3-5 倍差距。

Mo 队瓶颈是"指针移动的内存访问 + 函数调用开销"，优化围绕"减少移动、减少寻址、减少分支"展开；面试答出奇偶排序与内联数组化即体现工程素养，无需背具体指令。

• 按块分组、组内 r 单调的排序准则
• l 与 r 指针移动量的分别建模
• 对块大小求导取最优平衡点

Mo 队的排序准则是"按块分组、组内单调"：所有查询按 l/B 分块，块内按 r 排序（可加奇偶交替）。移动量分析：l 指针在同块内移动 ≤B、跨块跳变 ≤B，总 O(q·B)；r 指针在同一 l 块内单调移动 ≤n、跨块跳变 ≤n，共 n/B 个块，总 O((n/B)·n)。于是总移动量 T(B)=qB+n²/B，对 B 求导令 q-n²/B²=0，得 B=n/√q，此时 T=O(n√q)，是 L1（曼哈顿）距离和意义上的最优。

推导细节：q 个查询对应二维平面 (l,r) 上的 q 个点，按"列宽 B 的桶 + 行内排序"形成之字形路径，路径总长即指针移动总量；最优 B 使横向（qB）与纵向（n²/B）移动量同阶，得到 O((n+q)√q) 的复杂度（n、q 同阶时 O(n√n)）。

把指针移动总长建模为曼哈顿距离和、再对块大小求最优，是 Mo 队复杂度分析的通用模板；理解 B=n/√q 的出处（两方向移动量平衡）比死记块大小更有说服力，面试时应先写 T(B) 再求导。

• 只增不删 + 版本快照还原
• 按 l 块分组、r 单调扩展
• 与普通 Mo 相同的复杂度分析

回滚 Mo 队用于"add 容易、remove 困难"的数据结构（如维护最大值、不可逆的并查集、栈式计数）。它对每个 l 块独立处理：块内查询按 r 升序排序；对每个查询先把 r 指针从块右端向右扩展（只 add），l 指针则从块右端点向左临时扩展到 l（也只 add），记录答案后用快照/撤销栈把 l 侧临时加入的状态回滚到块右端点，再处理下一个查询。全程没有删除操作，只要求数据结构支持 add 与状态快照。

复杂度与普通 Mo 相同 O(n√q)：r 指针每块单调移动 O(n)，共 n/B 块；l 指针每次查询临时扩展 O(B)，共 O(qB)；取 B=n/√q 平衡。回滚借助快照在 O(1) 或 O(log n) 内还原，把"删除"替换为"版本还原"，是处理不可撤销结构的通用技巧。

回滚的本质是"只前进、可撤销"——把删除换成快照还原，牺牲一点常数换取数据结构简化；它与"只删不加"场景（如滑动窗口求 gcd 的单调性维护）是对偶技巧，面试时说出"按块分组 + 临时扩展 + 快照回滚"三步即可。

• 欧拉序进出两次的编码方式
• 路径转区间与 lca 特判
• 块大小 √(2n) 与排序准则

树上 Mo 队把路径查询编码到欧拉序：DFS 时每个节点入栈记 in[u]、出栈记 out[u]，序列总长 2n。查询路径 u→v 时按 in/out 组织区间：u 是 v 的祖先时用 [in[u], in[v]]，否则用 [out[u], in[v]] 且 lca 单独计入；区间内出现奇数次的节点集合恰为路径（除 lca 视情形外），用 vis 翻转维护贡献。

块分割对 2n 长度的欧拉序取块大小 B=√(2n)，按 (l/B, r) 排序后沿用普通 Mo 的移动框架；子树查询退化为 [in[x], out[x]] 单区间。正确性依赖"奇偶性 + 进出序"：非路径节点在区间内出现偶数次被抵消，路径节点恰好出现一次（祖先情形下 lca 也在区间内）。

与普通树上 Mo 的唯一差别是序列构造与 lca 特判；掌握"进出两次 + 奇偶抵消"即掌握树上 Mo 的全部要点，面试时先用小树手推一遍欧拉序更有说服力。

• ODT 的随机数据均摊与实现简单
• 懒标记线段树的最坏 O(log n) 保证
• 查询类型与数据生成方式的匹配

两者解决"彩色区间操作"的路线不同：ODT 用 set 维护同值连续段，操作靠 split/assign 的切分与合并，实现短小，支持任意"遍历段"型查询（区间幂和、第 k 小），但最坏 O(n) 每操作，依赖随机数据与高频区间赋值的均摊；Lazy Segment Tree 用懒标记下传保证任何数据下 O(log n) 每操作，但只支持可合并（幂等或线性可加）的聚合，实现更繁琐。

取舍准则：若数据随机且区间赋值是主要操作（CF 896C 型题面），ODT 代码量小、常数低；若需最坏复杂度保证、数据可被构造（CF 915E 型），或查询涉及区间翻转、区间取模等不可简单合并的操作，选 Lazy 线段树。工程上还有"线段树 + 颜色段均摊"的势能方案作为折中。

核心是"均摊 vs 最坏"与"实现成本 vs 通用性"的两组权衡；面试应明确指出 ODT 的复杂度前提（随机数据/赋值高频）而非无条件宣称 log 复杂度，这是区分水平的关键点。

• 笛卡尔树中序保下标、堆序保值的双不变量
• 区间最值节点 = 两下标节点的 LCA
• 欧拉序把 LCA 还原为深度 ±1 RMQ 的闭环

对数组 a[1..n] 构造笛卡尔树：以数组下标为二叉搜索树中序、以数组值为堆序（大根堆对应 RMQ 取 max）。关键性质：区间 [l,r] 的最值节点恰为下标 l 与 r 在笛卡尔树上的 LCA——由中序性，l、r 分居 LCA 的左右子树（或 LCA 即其一），LCA 的下标落在 [l,r] 内；由堆序性，LCA 的子树值最优且其子树下标区间覆盖 [l,r]。因此静态 RMQ 等价于两节点 LCA 查询。

欧拉序参与"LCA 再转 RMQ"的闭环：对笛卡尔树做 Euler Tour，深度序列相邻差恰为 ±1，LCA 即欧拉序区间深度最小点，于是 RMQ 又化为 ±1 RMQ，可用 Fischer-Heun 做到 O(1) 查询。整条链 RMQ→笛卡尔树→LCA→欧拉序→±1 RMQ 全程 O(n) 预处理，是"问题等价归约"的经典演示。

转化的根基是"中序保区间、堆序保最优"两条不变量；欧拉序的作用是把树上祖先问题还原为深度上的区间最值，使归约链闭合。面试时先讲笛卡尔树性质、再讲欧拉序的 ±1 化，逻辑最顺。

• 896C 的随机数据生成方式与操作类型
• 915E 的确定性数据与区间赋值模型
• 根据数据生成方式选择数据结构的判断

CF 896C（Willem, Chtholly and Seniorious）提供区间加、区间赋值、区间第 k 小、区间幂和四种操作，数据由固定随机种子生成且区间赋值操作占固定比例，是 ODT 的标准模板题：所有操作先 split 再遍历 set 段处理，随机数据下期望 O(n log n)。CF 915E（Physical Education Lessons）是"区间赋 0/1 + 查询全局 1 的个数"，可用 ODT 每次 assign 并维护全局答案，也可用线段树；但 915E 的数据并非随机生成，构造数据可使 ODT 段数膨胀到 O(n) 而退化。

对比结论：896C 考验"随机模型下的均摊实现"，915E 考验"最坏情况下的正确性选择"；同一份 ODT 代码在两道题上的命运不同（896C 可过、915E 可能 TLE），说明必须分析题面数据的生成方式再决定数据结构。

面试讲清"ODT 适用边界 = 随机数据/高频赋值"以及 915E 这类确定性数据下 ODT 可能退化的教训，比罗列代码更有价值；回答时以 896C 与 915E 为一正一反的例子最有力。

• split 只增段、不合并段的场景
• 交替赋值构造碎片段的反例
• 退化与随机模型的对立

ODT 的最坏退化来自 split 的开销无法被合并回收：若操作区间总是与现有段边界错开，每次 split 都把段切开而 assign 又不合并（或合并范围小于切开的范围），段数只增不减，最终可达 O(n)，任何操作都要遍历 O(n) 段。反例：初始 1 个段 [1,n]，交替执行 assign(l,r,v1) 与 assign(l,r,v2)（r<n），每次赋值都先 split(r+1)、split(l) 把段切开，两端碎片段 [1,l-1] 与 [r+1,n] 保留，段数每次 +2，最终 O(n) 段。

更简单的构造：按顺序对每个位置单独 assign（产生 n 个长度 1 的段），再执行跨所有段的查询，每次查询 O(n)。因此 ODT 在有序/对抗输入下退化为 O(n²) 量级，必须依赖随机数据下"赋值合并段"的均摊才能高效。

退化根因是"段数上界 O(n) 且无合并保证"——只有赋值把相同值相邻段合并时才回收段；理解反例即理解 ODT 的适用前提，面试时能当场构造交替赋值反例即可加分。

• 随机区间赋值下段数的期望负漂移
• 分支过程建模与后代期望小于 1
• Chernoff/union bound 给出高概率上界

在纯随机模型（操作区间均匀随机）下，设当前段数为 s，一次区间赋值覆盖期望约一半的段（覆盖长度期望 n/2），被覆盖的段被删除并由 1-2 个新段替代，故段数的期望净变化为负：E[Δs]≈-s/2+2。该负漂移使段数像"带反射壁的随机游走"稳定在低水平，配合 Chernoff/Hoeffding 界可得：t 次操作累计删除的段数（即总工作量的主要部分）高概率为 O(t)，再计入每操作 split 增加的常数段，总复杂度 O((n+q) log n) 以高概率成立。

严格证明的常见路径：把段数过程建模为分支过程（每个被覆盖段以某概率"存活"出 1-2 个新段），计算期望后代数 <1，则总后代数（段数增长总量）以指数概率有界，再用 union bound 覆盖全部操作。注意该分析依赖"赋值区间均匀随机"，对抗输入不成立。

期望负漂移 + 分支过程收敛是随机数据结构证明的两板斧；能说出"期望净变化为负、Chernoff 给出高概率上界"即抓住要点，面试无需背诵全部证明细节。

• 4 维表 f[k1][k2][i][j] 的预处理顺序
• 四个角子矩阵合并的 O(1) 查询
• 内存优化：行 ST + 分块折中

二维 Sparse Table 用四维表 f[k1][k2][i][j] 表示以 (i,j) 为左上角、宽 2^k1、高 2^k2 的子矩阵最值：f[0][0] 为原值，先按行倍增再按列倍增（或反之），预处理 O(nm log n log m)。查询 [x1,x2]×[y1,y2] 取 k1=⌊log2(x2-x1+1)⌋、k2=⌊log2(y2-y1+1)⌋，用四个角的子矩阵合并：min(f[k1][k2][x1][y1], f[k1][k2][x2-2^k1+1][y1], f[k1][k2][x1][y2-2^k2+1], f[k1][k2][x2-2^k1+1][y2-2^k2+1])，O(1) 查询，与一维相同只支持幂等聚合。

工程内存优化：四维表空间 O(nm log n log m) 较大，常用"先对每行做一维 ST、查询时对两行区间分别取 ST 结果再合并"的折中（O(nm log m) 空间 + O(log n) 查询），或对 4 维稀疏表做分块压缩；当某一维度很小时可退化为对行向量的普通一维 ST。

二维 ST 是"倍增在高维空间的直积"——每个维度的区间覆盖独立取幂等合并，四个角即可覆盖矩形；回答关键是讲清预处理顺序（先横后纵）与四角合并，以及空间与查询时间的折中方案。