随机化与近似算法

• 哈希碰撞攻击的原理与危害
• 随机化选择基数/模数防御
• 双哈希与自然溢出的防御结合

反哈希攻击的核心是让攻击者无法预测哈希参数。常用防御策略包括：使用大素数模数（如 10^9+7、10^9+9）并随机选择基数（base），使攻击者无法预先构造针对固定基数的碰撞对；采用双哈希（两个不同模数/基数组合）或三重哈希，将碰撞概率降到可忽略；对字符串哈希使用随机化基数，使每次运行都不同，从而让针对单一固定基数的卡哈希攻击失效。此外，可用自然溢出（unsigned long long 模 2^64）配合随机基数，但需注意模运算溢出后可能被精密构造，故更稳妥的是大素数模+随机基数。

攻击若能预制碰撞，哈希的 O(1) 期望就退化为 O(n) 最坏。随机化基数让攻击者无法离线构造碰撞集合，因为每次运行参数不同；双哈希让两个独立哈希同时碰撞的概率降到乘积量级，从而概率性保证正确。

• 树状数组的二进制提升原理
• 从高位到低位贪心累加
• 与普通二分查询的区别

树状数组上二分利用二进制提升（binary lifting）从最高位到最低位逐位尝试。维护一个当前下标 pos 和累计和 sum，初始 pos=0。对每个二进制位 i（从高到低），尝试 pos += 2^i，若该位置对应的树状数组节点值 sum + BIT[pos] < k，则接受该步并累加，否则放弃。最终 pos 就是前缀和首次 ≥ k 的位置减 1，答案即 pos+1。复杂度 O(log n)。

树状数组的每个节点 BIT[i] 保存的是 (i - lowbit(i), i] 区间的和，因此从高位到低位逐位累加可以贪心地逼近目标前缀和，且每次移动都保持意义完整。这等价于在 Fenwick 树上做二进制拆分的二分，比在树状数组数组上做两次普通二分（先求前缀和再二分）快一档。

• lowbit 运算的定义
• 前缀和分解成若干区间
• 每次查询跳过的区间数

树状数组查询前缀和时，从下标 i 开始不断执行 i -= lowbit(i)，并累加 BIT[i]。其中 lowbit(i) = i & (-i)，表示 i 的最低位的 1 所代表的数值。每次执行 i -= lowbit(i) 都会消去 i 二进制表示中最右边的一个 1，而一个数的二进制表示中最多有 O(log n) 个 1，因此前缀和查询最多累加 O(log n) 个节点的值，复杂度为 O(log n)。

位运算来源是"i 的二进制中 1 的个数"即为区间分解的段数。每减一次 lowbit 消去一个 1，而 int 类型最多 32 位、long 最多 64 位，所以查询次数有严格上界。这就是树状数组比线段树常数更小、实现更简洁的原因。

• 随机化验证的基本思想
• 用随机向量将矩阵乘法降维
• 错误概率与重复验证

Freivalds 算法验证 A×B=C：随机选取一个 n 维向量 r，其分量从 {0,1} 中随机选取（或更均匀的分布），计算 A(Br) 与 Cr。若 A×B=C，则 A(Br)=Cr 必定成立；若 A×B≠C，则 A(Br)≠Cr 的概率至少为 1/2（实际为 1/2 或更高）。因此只需三个矩阵乘向量运算，每次 O(n²)，重复 k 次后错误概率降至 ≤(1/2)^k，即概率化验证。

关键技巧是矩阵乘向量只需 O(n²)，而直接验证 A×B=C 需要 O(n³)。Freivalds 用随机向量把"矩阵相等"降维为"矩阵乘随机向量相等"，利用 Schwartz-Zippel 引理保证错误概率上界。重复几次即可把错误降到可忽略，同时保持 O(n²) 时间。

• 字符串哈希与滚动窗口
• 前缀哈希与滑动窗口更新
• 平均 O(n) 与最坏情况的说明

Rabin-Karp 先计算模式串的哈希值，再计算文本中所有长度为 m 的窗口的哈希值。利用滚动哈希，从窗口 [i, i+m-1] 滑到 [i+1, i+m] 时，只需减去出去的字符、乘以基数、加上新进来的字符，即可 O(1) 更新哈希。当窗口哈希等于模式哈希时，再进行逐字符 O(m) 确认（避免哈希碰撞带来的误报）。平均复杂度 O(n+m)，最坏 O(nm)。

滚动哈希把"每个窗口重新计算"的 O(nm) 优化为 O(1) 更新，从而整体 O(n)。好处是能一次扫描完成多个长度窗口查询，且可扩展支持多模式匹配；代价是哈希碰撞需二次确认，且模数选得不当时可能碰撞，故常用大素数模或双哈希。

• 树哈希的构造
• 随机化哈希避免碰撞
• 递归合并子树哈希

判定子树同构常用树哈希：对每棵子树计算一个哈希值，父节点的哈希由其子树哈希值组合而成。为避免不同子树结构计算出相同哈希，可对每个子树的哈希值进行排序后，用随机化方式（如乘以随机权重或随机基数的多项式）合并，或使用随机分配的层权值。两棵子树同构当且仅当其哈希值相等。随机化哈希大幅降低碰撞概率，且可结合大素数模数与随机基数。

树哈希把"判断子树结构是否相等"转化为"比较两个哈希值是否相等"，从而在 O(n) 内完成。关键是合并方式需对子节点顺序不敏感（常用排序后累加），且随机化参数让不同结构趋向获得不同哈希。相比朴素递归比较，可提前剪枝，常用于树的同构判定、子树匹配等题目。

• 随机化 pivot 对期望的影响
• 每次只处理一侧的递归
• 最坏退化情形

QuickSelect 每次 partition 后只递归处理包含目标元素的那一侧。若 pivot 在期望意义上把一个 n 元素数组分成大致相等两半，则递归规模 T(n) = T(n/2) + O(n)，解得 T(n) = O(n)。随机化选 pivot 让每次两侧大致均衡的概率较高，故期望 O(n)。但若每次 pivot 都恰好是最小/最大元素，则每次只淘汰一个元素，规模退化为 n + (n-1) + ... = O(n²)。

期望 O(n) 来自"随机 pivot 均衡划分"时每层只处理一侧的递推；最坏 O(n²) 来自 pivot 总是极端导致只缩小 1。随机化消除了"针对固定 pivot 的对抗输入"，但无法消除随机坏运气，故最坏仍是 O(n²)；要保证最坏 O(n) 需用 BFPRT（中位数的中位数）确定性 pivot。

• 势能函数 Φ 的选取
• chmin 操作下 Φ 的递减
• 总复杂度 O(n log² n) 的来源

线段树 Beats 的复杂度证明基于势能函数 Φ = Σ log(区间内不同值的个数) 或类似量。对节点执行 chmin（区间取 min）时，若节点最大值严格大于要取的值，则节点内不同值的个数下降，势能严格减少；每个节点每次"被真正修改"都消耗势能。由于每次操作遍历的节点数有限，且势能总下降有界，总复杂度为 O((n+q) log² n)。维护区间最大值、次大值及最大值个数，使 chmin 高效。

核心思想是"势能分析"：日常意义上的昂贵操作（实际修改节点）必然消耗势能，而势能总量有界，因此总工作量有界。Beats 通过记录最大值/次大值/最大值个数，让 chmin 只在不触碰最大值时快速返回，只在真正需要时下推，从而把整体复杂度压到 O(n log² n)。

• 莫队排序规则
• 左右指针移动次数分析
• 均摊复杂度 O(n√n)

莫队把数组按块大小 B=√n 分块，对查询按"左端点所在块"升序、块内按右端点升序（或奇偶交替）排序。左指针在同一块内移动最多 O(B) 次，跨块移动 O(n) 次，共约 O(n·(n/B)) 次；右指针在每块内单调，每块移动 O(n) 次，共 O(n·(n/B)) 次。取 B=√n 时总移动次数为 O(n√n)，即均摊每次查询约为 O(√n)。

排序让移动成本均摊：左指针被块限制在局部，右指针在每块内单调不来回，从而避免最坏 O(n·q) 的来回移动。奇偶排序进一步减少右指针回扫。块大小取 √n 平衡了左右指针的移动量，是均摊 O(n√n) 的关键。

• 离散化与值域线段树
• 历史版本构建
• 区间差分的第 K 大查询

静态数组区间第 K 小：先把数值离散化，构建值域线段树。从左到右依次插入每个元素，每插入一个元素就产生一个新版本（可持久化线段树根节点），版本 i 表示前 i 个元素的权值分布。查询区间 [l, r] 的第 K 小：用版本 r 的线段树减去版本 l-1 的线段树，得到区间内各权值的频数，再在值域线段树上二分：若左子树计数 ≥ K 则下到左子树，否则 K 减去左子树计数后下到右子树，直到叶子。复杂度 O((n+q) log n)。

主席树的核心是"版本差"：两个版本的线段树之差即区间 [l,r] 的统计。每插入一个元素只新建 O(log n) 个节点（共享其余子树），因此空间 O(n log n)。值域上二分天然支持第 K 小查询，比"分块+每次二分"更优。

• 块内无序 vs 有序
• 查询类型：最大值/计数/区间 K 小
• 修改复杂度权衡

若查询只需找某块内的最大值、修改点或非边界暴力，块内无需有序，修改 O(1) 打标记即可。若查询需要"块内小于某值的个数"或"区间第 K 小（块内二分）"，则块内需有序，每次整块修改后需要在 O(√n log √n) 内重建块排序。维护有序的好处是查询块内可二分 O(log √n)，代价是修改后重建块、以及块内二分修改的复杂度。

取舍核心是"块内有序"用修改复杂度换取查询复杂度：不适于频繁整块修改却需要有序二分的情形；当查询多为"块内计数/二分"、修改较少时，维护有序更划算。若查询只统计整块最大值或总和，则无需排序，维护整块标记即可 O(1)。

• 大素数模的碰撞安全性
• 自然溢出的特性与缺陷
• 卡哈希攻击的差异

大素数模（如 10^9+7、10^9+9）用模运算截断哈希，结果在 [0, MOD) 内，只要基数随机且素数足够大，随机碰撞概率低，但理论上仍可被构造碰撞。自然溢出用 unsigned long long 自动截断到 2^64，速度极快、实现简单，但碰撞空间是 2^64，且存在已知的"卡自然溢出"构造方法（利用模 2^64 的线性同余性质构造等长碰撞对），因此对抗性输入下风险更高。实践常采用"大素数模 + 随机基数"或"双哈希"来兼顾安全。

大素数模核心优势是随机化后碰撞难以构造，风险来自模数小（2^32）时可能的碰撞；自然溢出优势是速度快，风险是模数结构特殊（2 的幂）易于被精密构造碰撞。安全取舍在于：随机化基数 + 大素数模，或用双哈希降低整体碰撞概率。

• lowbit 定义与含义
• 更新时 i += lowbit(i)
• 查询时 i -= lowbit(i)

lowbit(i) = i & (-i) 表示 i 在二进制中最低位的 1 所代表的数值。树状数组 BIT[i] 存储区间 (i - lowbit(i), i] 的和。更新位置 i 增加 delta 时，从 i 开始不断执行 i += lowbit(i)，把 BIT 中所有包含该位置的节点都加上 delta，复杂度 O(log n)。查询前缀和 sum(i) 时，从 i 开始不断执行 i -= lowbit(i) 累加 BIT[i]，复杂度 O(log n)。区间 [l,r] 的和 = sum(r) - sum(l-1)。

lowbit 确定了每个节点覆盖的区间，同时决定了更新向上传播的路径和查询向下合并的路径。加 lowbit 沿树向上跳，减 lowbit 沿树向下合并，两条路径都只有 O(log n) 步，因此单点更新与区间查询同为 O(log n)。

• 固定 pivot 的对抗输入
• 随机化消除对抗性
• 期望复杂度保证

若 pivot 固定（如取第一个元素），攻击者可以构造使每次划分都极不均衡的输入，导致最坏 O(n²)。随机选 pivot 使每次划分的 pivot 位置不固定，任何输入都无法预先确定每次划分的规模，因此消除了"针对固定 pivot 的对抗输入"。随机化使划分在期望意义下大致均衡，快速排序期望 O(n log n)，快速选择期望 O(n)。

随机化把最坏情况从"确定性输入导致的必然退化"变成"概率极低的坏运气"，从而保证期望复杂度。虽然最坏仍可能是 O(n²)（概率极低），但不再被特定输入触发。这是随机化算法"使最坏对抗输入失效"的典型运用。

• 集合覆盖问题与贪心策略
• 每次选覆盖未覆盖最多元素的集合
• 近似比 H(n) 的证明

集合覆盖贪心算法每次选择能覆盖最多当前未覆盖元素的集合。其近似比 H(n) 的证明：设在贪心过程某一时刻仍有 k 个未覆盖元素，最优解用 OPT 个集合就能覆盖全部，因此最优解中必有一个集合覆盖至少 k/OPT 个未覆盖元素，故贪心每次至少覆盖 k/OPT 个，代价按调和数累加。最终贪心使用的集合数 ≤ H(n)·OPT，其中 H(n)=1+1/2+...+1/n。

H(n) 来源于"每轮覆盖比例至少 1/OPT"的贪心保证，导致总轮数按调和级数累加。这是经典"贪心近似比"证明：用最优解给贪心每步的进步设下界，从而上界贪心总代价。H(n) 是集合覆盖在一般情形下能得到的近似比（除非 P=NP）。

• 动态分配节点
• 稀疏区间表示
• 空间复杂度 O(q log n)

普通线段树需预分配 4n 个节点，值域 10^9 时无法预分配。动态开点线段树只在实际访问（插入/查询）时创建节点，每个节点记录左右子节点下标，仅当需要时才 new 出子树。因此只创建 O(操作次数 × log 值域) 个节点，空间随操作数增长而非值域大小增长。查询时从根向下，若某子树未被创建则视为空/0 处理。

动态开点把空间从 O(值域) 降到 O(q log 值域)，因为只创建被访问的路径节点。值域 10^9 时 log 值域约 30，每操作最多创建 30 个节点，空间可控。常与可持久化结合使用，或用于权值线段树、值域巨大时的区间统计。

• 两个独立哈希组合
• 碰撞概率相乘
• 选择合适的模数/基数

双哈希用两个独立的哈希函数（如不同的大素数模数或不同基数），对同一输入分别计算 h1、h2，只有当 h1 和 h2 都碰撞时才发生误判。若单个哈希碰撞概率为 p，双哈希碰撞概率约为 p₁·p₂，两个独立事件概率相乘，数量级大幅下降。例如单哈希碰撞概率 10^-9，双哈希可降到 10^-18 量级，工程上可忽略。

关键是两个哈希"独立"：独立随机变量的联合碰撞概率是各自概率的乘积。双哈希增加了存储/计算开销（内存翻倍），但安全性大幅提升。实际中常选择两个不同的大素数模数（如 10^9+7 与 10^9+9）+ 不同基数，避免参数相关性。

• 数据规模巨大的场景
• 采样的代表性
• 近似精度与延迟交换

在线广告/推荐面临海量用户与物品、实时延迟要求，精确计算（如全量 CTR 统计、全量相似度计算）代价过高。利用采样（如对流量采样、对用户行为采样）估计点击率、用户特征分布；用近似算法（如负采样、近似最近邻 ANN、Top-K 近似）在可接受误差内快速得到结果。近似将计算复杂度从 O(n²) 降到 O(n) 或亚线性，用"误差预算"换取实时性。

核心权衡是"精度 vs 延迟/成本"。广告出价、推荐排序往往只需相对排序而非绝对精确值，采样与近似能在大规模下保持可用性。近似算法（如 Bloom 过滤器、HyperLogLog、ANN）和采样保证误差上界，适合在线场景。

• 块大小与查询数量的关系
• 权衡左右指针移动
• 实际常数优化

莫队中若查询数为 m，块大小取 n/√m 可在理论上平衡左右指针移动，使总复杂度更紧；取 √n 是 m 与 n 同阶时的简化选择。实际中块大小影响常数：块太小则左指针跨块次数多，块太大则右指针每块内移动多。当 m 与 n 差异大时，用 n/√m 更优；二者同阶时 √n 与 n/√m 等价。实际速度还受缓存、常数影响，需实测微调。

总移动次数 ≈ n·(m/B) + B·m，对 B 求导得 B = n/√m 时最优。√n 是假设 m≈n 时的特例。块大小是常数级优化，不改变复杂度量级，但显著影响实际运行时间，故常按 n/√m 或实测微调。

• 问题分类（P/NP-hard）
• 近似算法的近似比概念
• 明确说明上下界

说明要点：第一，指出该问题属于 NP-hard（如 TSP、集合覆盖、顶点覆盖），在 P≠NP 假设下不存在多项式精确算法，因此只能近似。第二，给出已知近似算法的近似比（如顶点覆盖 2-近似、集合覆盖 H(n)-近似），说明近似算法的复杂度与逼近方向和紧度。第三，说明近似比的下界（已知不可能近似到某个比例，除非 P=NP），从而定量说明"只能近似到某程度"。

面试官考察的是能否严谨区分"精确不可行"与"近似可行且界已知"。关键要给出量化近似比（α 满足 OPT ≤ 近似解 ≤ α·OPT 或方向相反），并说明下界（inapproximability），从而证明"只能近似且已知界"。这体现对复杂度与近似理论的掌握。

• 分块核心思想
• 整块操作 O(1) 或 O(√n)
• 小块暴力 O(√n)

分块把长度为 n 的数组分成 B 块，每块大小约 n/B。一次区间操作：完全覆盖的整块用懒标记或预处理整体处理（O(块数)），两端不足一块的散块直接暴力（O(B)）。若 B≈√n，则整块数约 √n、散块大小约 √n，一次操作总复杂度 O(√n)。通过"整块聚合、散块暴力"证明总复杂度 O((n+q)√n)。

复杂度证明依赖块大小平衡：块数 O(n/B) 与散块长度 O(B) 这两项，取 B=√n 时两者都约为 √n，一次操作 O(√n)。这就是"大块整体、小块暴力"的数学本质——整块操作数与散块元素数之和被 √n 均衡。

• 差分数组思想
• 两个 BIT 的结合
• 区间加与区间和公式

用差分思想：区间 [l, r] 加 v 等价于在差分数组上加两处（d[l]+=v, d[r+1]-=v）。为支持区间和查询，维护两个 BIT：BIT1 存差分 d[i]，BIT2 存 i·d[i]。前缀和公式为 sum(x) = (x+1)·Σd[i] - Σ(i·d[i])，因此区间和 [l,r] = sum(r) - sum(l-1)。区间加 O(log n)，区间和查询 O(log n)。

单个 BIT 的差分只能做"区间加 + 单点查询"。要支持区间和，需用第二个 BIT 记录 i·d[i] 以修正差分前缀和的偏差。两个 BIT 分别维护 Σd 和 Σ(i·d)，组合即可 O(log n) 求区间和。

• 集合哈希的构造
• 随机权重
• 概率正确性

为每个元素分配一个随机权重（或随机哈希值），集合的哈希定义为所有元素权重的某种组合（如异或或和）。两个集合相等则哈希必相等；若集合不等，由于权重随机，哈希相等的概率极低。用异或时，若元素出现次数为偶数会抵消，故需结合出现次数或采用"和 + 随机权重"并对每个元素累加。常用于判断多重集相等、DNA 片段等。

随机化哈希把"集合相等"的精确 O(n) 比较降为 O(1) 哈希比较，概率虽非 1 但误差可忽略。关键是权重随机且独立，使不同集合哈希碰撞概率低。若元素可重复（多重集），需用乘法或计数累加而非简单异或。

• 分组五元素找中位
• 递归选择
• 期望 O(n) 或确定 O(n)

求中位数可用"分组中位的中位"（median of medians）：把数组每 5 个一组，求每组中位数，再递归求这些中位数的中位数作为 pivot，进行 partition 后递归到包含第 k 小元素的一侧。该 pivot 保证每侧至少淘汰约 3n/10 个元素，从而递归规模有界，最坏 O(n)。若随机选 pivot 则期望 O(n)。这是 BFPRT 的确定性版本，中位数即第 n/2 小的元素。

关键在于 pivot 的质量保证：每 5 个一组取中位，再取中位的中位，保证至少 3n/10 个元素在中位两侧，从而最坏递归 T(n) ≤ T(n/5) + T(7n/10) + O(n)，解得 O(n)。随机化版本则用随机 pivot 将期望降到 O(n)。

• 多项式哈希公式
• 模数选择与冲突概率
• 双哈希降冲突

多项式滚动哈希 h = ((h·base + c) mod MOD)，把字符串编码为 base 进制数再取模。取模分大素数模（如 10^9+7、10^9+9）与自然溢出（2^64）。冲突概率与模数大小相关：模数越大、随机基数下冲突概率越低。大素数模下随机碰撞概率约 1/MOD；自然溢出下约 1/2^64。实际用双哈希（两个独立模数）可把冲突概率降到乘积量级。

冲突概率核心是"模空间中发生误判的概率"。基数需与模数互质且随机化，避免卡哈希。大素数模安全性高于 2^32 的自然溢出，但低于 2^64；双哈希组合进一步降低。工程上常用"大素数模 + 随机基数"或双哈希。

• 权值线段树与离散化
• 第 K 小查询
• 逆序对统计

先把数值离散化，构建权值线段树（每个节点存该值域内元素个数）。求第 K 小：从左子树元素个数判断，若左子树计数 ≥ K 则下到左子树，否则 K 减左子树计数后下到右子树，O(log n)。求逆序对：从左到右扫描，每个元素 ans += 已插入中大于它的个数，即总数 - 已插入 ≤ 它的个数，再插入该元素，O(n log n)。

权值线段树通过值域上的计数二分支持第 K 小；逆序对的核心是"当前元素之前且比它大的元素个数"，用权值线段树做区间查询即可。离散化把值域压缩到 n，使线段树节点数 O(n)。相比树状数组，权值线段树更直观支持区间统计。

• 离线排序策略
• 左右指针移动分析
• 块大小取 √n

莫队把查询离线，按特殊顺序排序：先按左端点所在块，块内按右端点排序（奇偶块交替）。这样左指针在同一块内移动受限（O(√n) 内），右指针在每块内单调移动。总的左移动约 O(n·√n)，右移动约 O(n·√n)，取块大小 √n 时总复杂度 O(n√n)。移动过程中对区间进行增删维护当前答案。

把"回答所有查询"转换为"移动左右指针的总代价最小化"。排序使指针移动局域化、单调化，避免来回。复杂度 O(n√n) 是左/右指针移动量之和，块大小 √n 平衡两者。奇偶分块进一步减少右指针回扫。

• 蒙特卡洛：结果可能错误，时间确定
• 拉斯维加斯：结果一定正确，时间随机
• 两者转化关系

蒙特卡洛（Monte Carlo）算法在固定时间内运行，但结果可能以一定概率出错（错误概率可用重复降低）；拉斯维加斯（Las Vegas）算法保证结果一定正确，但运行时间随机（期望时间有界）。典型例子：随机 QuickSelect 是拉斯维加斯（结果正确，时间期望 O(n)）；Freivalds 矩阵验证是蒙特卡洛（可能误判，时间固定 O(n²)）。

关键区别是"错误源"：蒙特卡洛错在结果，拉斯维加斯错在时间。拉斯维加斯可通过"在超时后重跑"转成蒙特卡洛；蒙特卡洛通过重复验证并取多数，可在一定概率下转成拉斯维加斯。理解两者对选择随机算法很重要。

• 最大化/最小化问题方向
• 近似比 α 的定义
• OPT 与近似解的关系

对最小化问题，近似算法输出解的成本 C 满足 C ≤ α·OPT（α ≥ 1），即近似解不超过最优解的 α 倍；对最大化问题，近似解价值 C 满足 C ≥ OPT/α（等价于 OPT ≤ α·C），即近似解不低于最优解的 1/α。α 越小近似越好，α=1 即精确。方向取决于问题是最小化还是最大化，但统一用"OPT 被近似解包围在 α 因子内"。

近似比刻画近似解与最优解的距离，方向由优化目标决定：最小化看"上界"，最大化看"下界"。对于极小化问题，常用 ρ 表示近似解 ≤ ρ·OPT；极大化问题表示为 OPT ≤ ρ·近似解。理解方向才能正确比较近似算法的优劣。

• 元启发式的适用场景
• 局部最优与全局搜索
• 大规模问题的近似解

对 NP-hard 且大规模（如大规模 TSP、调度、布局）问题，精确算法或带近似比算法无法在合理时间内求解。元启发式（遗传、蚁群、模拟退火、粒子群）通过群体搜索、随机扰动、局部搜索结合，在大规模下快速得到一个可行且较优的近似解，虽无严格近似比保证，但工程上常能接近最优。适合对"解质量"要求高但"时间"要求更快、且无理论近似比可用的场景。

元启发式的价值在于"在时间预算内找到好解"，而非证明近似比。它们不保证最优，但通过探索-利用平衡和大规模并行搜索，能处理精确算法无法企及的规模。实际价值体现在工程部署、实时调度与资源受限场景。

• PRNG 的种子与序列
• 可复现性
• 随机数质量对算法影响

伪随机数生成器（PRNG）用种子确定序列，相同种子产生相同序列，从而保证可复现性（固定种子可复现实验结果）。PRNG 质量影响随机性：质量差的 PRNG 可能周期短、有相关结构，导致随机算法分布偏差、影响性能与正确性。好的 PRNG（如 xorshift、MT19937、Java 的 SplittableRandom）周期长、分布均匀。工程与实验需固定种子保证可复现，同时用高质量 PRNG 保证随机性。

可复现性依赖"种子可固定"，随机性依赖"PRNG 质量"。两者可兼得：固定种子 + 高质量 PRNG。对随机算法的复杂度与实验，PRNG 的质量影响实际分布；若循环相关导致偏差，可能使随机化失效。因此既要可复现又需高质量随机源。

• 期望复杂度的推导
• 错误概率的量化
• 随机化参数的选择

论证期望复杂度：建立递推（如 QuickSelect 的 T(n)=T(n/2)+O(n)），说明随机 pivot 使划分期望均衡，从而期望 O(n)；说明最坏情况只在概率极低的坏运气下发生。论证可靠性：量化错误概率（如双哈希碰撞概率 1/MOD²，重复 k 次后 (1/2)^k），说明可通过重复或调整参数将错误降到可忽略。强调随机化消除对抗输入而非依赖运气。

面试官关注两点：一是期望复杂度为何成立（随机化的均衡性），二是零或极小错误概率如何保证（重复、独立试验、双哈希）。用"期望推导 + 概率界"双线论证，可体现对随机化算法的严谨理解。可对比确定性最坏情况，说明随机化权衡。

• 贪心选边策略
• 匹配与顶点覆盖的关系
• 近似比 2 的证明

算法不断随意选一条未被覆盖的边，把它的两个端点都加入覆盖集，并从图中移除。这样选出的边构成一个极大匹配（任意两条不相邻）。设匹配大小为 k，则覆盖集大小 2k。由于每条匹配边都需要一个不同顶点去覆盖，最优覆盖至少 k 个顶点，即 OPT ≥ k，因此 2k ≤ 2·OPT。这是 2-近似。

证明关键是"选出的边集是匹配"且"最优覆盖必须覆盖每条匹配边至少一个端点"，故 OPT ≥ 匹配大小。而算法用 2k 个顶点覆盖全部，故 2k ≤ 2·OPT。对一般图这个 2 界是紧的（除非 P=NP）。

• 大素数减少碰撞
• 与基数互质
• 乘法逆元

大素数作为模数：一是模空间大，随机碰撞概率低（约 1/MOD）；二是素数保证与任意非 MOD 倍数的基数互质，使多项式哈希的数学性质更干净；三是素数模下存在乘法逆元，便于做除法运算（如滚动哈希除以基数）。10^9+7 与 10^9+9 都是接近 2^30 的素数，int 范围内乘法不溢出，适合快速计算。

大素数兼顾"碰撞概率低"与"代数性质好"。素数确保乘法群结构，逆元存在；接近 2^30 使模运算在 long 内不会溢出。10^9+7 与 10^9+9 是竞赛常用组合，双模可进一步降低碰撞。

• 负载均衡问题
• 贪心（移到当前最轻机器）
• 最优拟合（LPT）近似比

负载均衡目标是把任务分配到 m 台机器使最大负载最小（NP-hard）。贪心算法按任意顺序把每个任务放到当前负载最轻的机器上；最优拟合（LPT）算法先将任务按处理时间降序排列，再依次放到当前最轻的机器。LPT 的近似比为 4/3 - 1/(3m)，贪心（序列限制）近似比为 2。复杂度 O(n log n + n log m)。

贪心保证近似 2（因最重任务的机器负载上界），LPT 通过"先排大任务"优化到 4/3。近似比来源是"最优解下界"（平均负载与最大任务）的对比。这类问题常用贪心近似，在调度中很常见。

• 爬山法的局部最优缺陷
• 随机重启的作用
• 两者结合

爬山法从某初始解出发，贪心移动到邻居中更优的解，直到到达局部最优（无邻居更优）。缺点是容易陷入局部最优而非全局最优。随机重启从多个随机初始解分别执行爬山法，取所有局部最优中的最佳者，从而增大找到全局最优或更好解的概率。随机重启是克服爬山法局部最优的常用手段。

爬山法"确定性贪心"易被困；随机重启通过"多个随机起点 + 独立爬山"提高探索到好解的概率。它不保证全局最优，但在工程上（如量子计算、组合优化）能有效提升解质量。与模拟退火等"概率接受劣解"的思路互补。

• Metropolis 接受概率
• 高温探索、低温利用
• 温度衰减调度

Metropolis 准则以概率接受比当前解差的解：接受概率 = exp(-ΔE/T)，其中 ΔE 是代价增量，T 是温度。高温时接受概率高，算法广泛探索搜索空间；低温时接受概率低，算法收敛于局部最优（利用）。通过温度衰减（从高温逐步降到低温），实现"前期探索、后期利用"的平衡，这是模拟退火的核心机制。

温度控制随机扰动幅度：高温允许跳出差解（探索），低温拒绝劣解（利用）。合适的降温调度（如几何衰减）在探索与利用间取得平衡，避免过早陷入局部最优或过于发散。这是模拟退火跳出局部最优的关键。

• PTAS 定义
• FPTAS 定义
• 对 ε 与输入规模的依赖

PTAS（多项式时间近似方案）对任意固定 ε>0，能在多项式时间内给出 (1+ε) 近似，但复杂度可能是 (1/ε) 的指数级（如 n^(1/ε)），ε 与输入规模 n 相关地昂贵。FPTAS（完全多项式时间近似方案）要求复杂度是 (1/ε) 与 n 的多项式，即多项式在 n 与 1/ε 上（如 O(n³/ε)）。FPTAS 是更强的近似方案，通常只对某些问题（如背包）存在。

区别在 ε 的影响：PTAS 中 ε 可进入指数（如 n^(1/ε)），FPTAS 中 ε 只进多项式（如 1/ε）。FPTAS 对 ε 更友好，但更稀少。若问题有 FPTAS，则其能任意逼近最优；若只有 PTAS，则 ε 变小时成本急剧上升。

• 一般 TSP 允许任意边权
• 常数近似可判定汉密尔顿回路
• 归约论证

一般 TSP 允许任意边权（连三角不等式都不满足）。若存在常数近似 α 的算法，则用它可判定汉密尔顿回路问题：构造一个图，若存在汉密尔顿回路则边权为 1，否则某些边权设为很大（如 α·n）。近似算法会因回路是否存在而给不同答案，从而 O(poly) 解决汉密尔顿回路，这要求 P=NP。因此一般 TSP 无常数近似（除非 P=NP）。

关键是"三角不等式不满足时，近似比与判定 NP 完全问题挂钩"。通过把少数边权设到极大，使近似算法能区分"有无汉密尔顿回路"，从而把 NP-hard 判定归约到近似。只有满足三角不等式（metric TSP）时才存在常数近似（如 MST 翻倍 2-近似）。

• 精确建模的困难
• 目标函数复杂
• 随机优化适应性

调度与布局问题常涉及大量约束、复杂目标（如非线性、多目标、不可解析表达）、大规模搜索空间，精确建模与求解代价极高或不可行。随机优化（模拟退火、遗传、粒子群）只需"能评估解的好坏"即可，不需要梯度或解析模型，通过随机扰动逐步改进，能适应复杂、非凸、约束强的问题。因此工程上常选随机优化。

随机优化的优势是"黑箱友好"：只需代价函数可计算，无需可微/凸性。对复杂约束与多目标，它通过随机搜索和局部改进找到可行且较优解。虽然无近似比保证，但对难以精确建模的实际问题更实用。

• 独立重复试验
• 错误概率相乘
• 指数级降低

若随机算法单次错误概率为 p（如 1/2），独立重复 k 次并取多数结果，则全部错才失败，错误概率为 p^k（或更小）。p=1/2 时，重复 k 次错误概率为 (1/2)^k，随 k 指数下降。例如失败概率 1/2^20 < 10^-6。这是因为独立试验的联合失败概率是各次概率之积，指数级衰减。

概率相乘是指数级降低的基础。重复 k 次"独立同分布"试验，同时失败概率为 p^k。工程上取 k=20~40 即可把错误降到远小于硬件故障率。这在蒙特卡洛降错、Freivalds 验证、指纹检测中广泛应用。

• 不可变数据结构
• 持久化（共享未修改部分）
• 函数式环境下的好处

函数式编程强调不可变数据（一旦创建不再修改）。"持久化"数据结构在不修改原数据的前提下，通过共享未改变的部分、只复制被修改的路径，生成新版本。二者天然契合：持久化结构依赖不可变性来安全共享节点，不可变数据结构借助持久化实现"修改"（实为生成新版本）。例如可持久化线段树、persistent 链表。

不可变是"允许共享"的前提——若节点可变，共享会互相影响。持久化通过路径复制 + 共享，实现 O(log n) 的"修改"，同时保留旧版本。二者结合使函数式数据结构高效且安全，是算法竞赛与函数式语言（如 Haskell、Clojure）的基石。

• 合并信息困难
• 线段树的局限
• 分块的暴力预处理

线段树要求区间信息可高效合并（如和、最大值、GCD）。当信息难以合并（如众数、mode、区间内出现次数最多的数）时，合并代价高，线段树不再适用。分块可以预处理"块与块之间"的信息（如块间众数表），整块查询用预处理结果，散块暴力补齐，从而 O(√n) 查询。分块是"暴力 + 预处理"的通用手段，适合难以合并的信息。

分块的优势在于"块内信息可暴力维护、块间信息可预处理"，不要求严格的合并律。对众数等"难以合并"的信息，分块用 O(n√n) 预处理 + O(√n) 查询解决，而线段树无法高效合并。这是分块替代线段树的关键场景。

• 块内有序维护
• 懒标记
• 整块二分 + 散块暴力

维护每块的有序数组（排序后的块内元素）与懒标记 add。整块加时懒标记累加，不重建；散块加时暴力更新元素并重建该块排序。查询"区间小于 K 的个数"：整块在有序数组上二分（用 K - add 定位），散块直接暴力统计。整块操作 O(√n log √n)，散块 O(√n)，总 O((n+q)√n log √n)。

核心是"块内有序 + 懒标记"：排序版本支持整块二分，懒标记使整块加 O(1)。散块少量元素暴力并重建。这套"整块二分、散块暴力"是分块维护区间计数与序关系的通用套路。

• 块大小的选择
• 整块与散块处理
• 复杂度平衡

分块把 n 个元素分成约 √n 块，每块约 √n 个元素。一次区间操作：覆盖的整块数约 √n，两端散块各约 √n 个元素。整块用预处理/懒标记 O(1)（或 O(√n)）处理，散块暴力 O(√n)。取块大小 √n 使"整块数"与"散块长度"都约为 √n，从而一次操作 O(√n)，在查询与修改之间取得平衡。

复杂度平衡的关键是块大小 B：整块数 O(n/B)、散块长度 O(B)。令两者相等求 B=√n，此时一次操作 O(√n)。这就是"√n 平衡查询与修改"的本质——把复杂度均摊到整块与散块各贡献 √n。

• 可持久化 Trie 结构
• 区间异或最值
• 带版本查询

可持久化 Trie 按二进制从高位到低位构建，每个版本对应前缀插入的结果。查询区间 [l,r] 内与 x 异或的最大值：用版本 r 减版本 l-1 判断某位是否有人，贪心从高位选与 x 相反位，若存在则走该分支，从而得到异或最大值，O(log V)。也用于带版本的第 K 大、出现次数等查询。

可持久化 Trie 用"版本差"表示区间内元素集合，配合"异或贪心从高位选相反位"求最大异或对。空间 O(log V) 每插入。是区间异或最值、可持久化字典序问题的标准工具。

• 可持久化数组表示父指针
• 按秩合并或启发式合并
• 版本回滚

可持久化并查集用可持久化数组（可持久化线段树）存储每个节点的父指针与秩，每次 find 沿父指针查询时，通过可持久化数组读取历史版本。合并时用按秩合并（或启发式合并），保证树高 O(log n)，从而 find 复杂度 O(log n)。由于 parent 数组可持久化，每次 union 产生新版本，支持回滚到历史版本。常不进行路径压缩（因压缩需修改多个节点、产生新版本），而用按秩合并保证 O(log n)。

路径压缩在可持久化中代价高（改多个父指针、产生新版本），故常只用按秩合并保证深度 O(log n)，find 变为 O(log n) 而非 O(α)。版本回滚通过"可持久化数组记录每次修改"实现，常用于带撤销的动态连通性。

• 路径复制
• 共享未修改子树
• 空间复杂度 O(n log n)

可持久化线段树每次更新只修改值域路径上的 O(log n) 个节点。创建新版本时，只新建这 O(log n) 个节点，其余节点（未被修改的子树）直接复用旧版本对应节点，即共享。这样每个版本只增加 O(log n) 空间，n 个版本总空间 O(n log n)，而非 O(n²)。各版本根节点记录版本起点。

关键思想是"路径复制 + 共享"：修改沿根的路径复制，其他子树共享。由于每次只改 O(log n) 个节点，共享大量未变子树，空间从 O(n·版本数) 降到 O(n log n)。这是可持久化数据结构的通用空间优化。

• 保留历史版本
• 避免共享被破坏
• 路径复制

可持久化要求保留所有历史版本，若原地修改节点，会破坏之前版本使用的节点，导致历史版本被改变。因此采用"新建节点"：修改路径上复制新节点，指向新的子节点，未修改子树仍共享。这样旧版本不受影响，新版本独立。新建节点是持久化的必然选择，代价是空间 O(log n)。

原地修改会破坏不可变性/历史版本，这与持久化目标冲突。新建节点 + 路径复制能同时保留旧版本并生成新版本，且共享未变部分几乎不浪费空间。这是可持久化数据结构的核心设计。

• 版本与时间点映射
• 版本间差分
• 历史区间查询

把每次修改映射为一个版本（根节点）。要查询"时间 t 时的区间 [l,r] 信息"，用版本 t 的线段树在 [l,r] 上执行区间查询。若要查"某时刻与另一时刻的差"（如区间第 K 小、区间内出现的值），用两版本根节点的线段树做差分运算。每个版本保存对应历史时刻的完整信息状态。

可持久化线段树把"时间维"变成"版本维"，每个版本记录该时刻的状态。历史查询只需在对应版本根上做标准区间查询或用版本差计算区间统计。空间 O(n log n)，时间 O(log n) 每查询。

• 区间最值（最大值/最小值）
• 历史最值
• 区间 GCD

区间最值：线段树节点存区间最大值/最小值，合并取 max/min，可支持区间查询。区间 GCD：节点存区间内所有数的 GCD，合并取 gcd，支持区间 GCD 查询与单点修改。历史最值（如历史最大值）：需要额外维护历史最值标记，配合懒标记记录"历史上推送到该节点的最大加值"，在区间加等操作下更新历史最值，通常用线段树 Beats 或额外历史标记实现。

区间最值与 GCD 都是可合并信息（max/min/gcd 满足结合律），只用简单线段树即可。历史最值需要额外记录历史极值及"历史最大标记"，因为普通懒标记只记录当前待加值，无法反映历史最大。历史最值常配合势能/Beats 处理。

• 双数组计数
• 增删对计数的影响
• 莫队维护

维护两个数组：cnt[x] 表示元素 x 的出现次数，freq[k] 表示"出现次数恰好为 k 的元素个数"。新增元素 x 时，先 freq[cnt[x]]--，再 cnt[x]++，再 freq[cnt[x]]++；删除同理反向。这样查询"出现次数为 c 的元素个数"即 freq[c]，O(1)。莫队每移动指针 O(1) 更新时间，总体 O(n√n)。

用"频数的频数"结构：cnt 记录每个元素出现次数，freq 记录出现次数为某值的元素个数。增删时同步更新 cnt 与 freq，保证查询 O(1)。这是莫队统计类"众数/频数分布"问题的标准维护方式。

• 下界/上界估计 OPT
• 对偶问题
• 紧度评估

评估近似解质量，需知道 OPT 的大致范围。对最小化问题，用下界估计 OPT（如对偶问题的最优值、松弛、贪心下界），近似解与下界的比值能上界近似比；对最大化问题用上界。若下界与近似解接近，则近似质量高。对偶（如线性规划对偶）天然给出 OPT 的下界/上界，据此判断近似解与 OPT 的差距。

精确 OPT 往往不可得，但可用"下界/上界/对偶"逼近 OPT。近似比 = 近似解 / 下界（最小化）可给出上界，从而评估近似质量。紧度指界是否可达到：若下界与近似解相差很小，说明近似接近最优。精确算法（如分支定界）也用下界剪枝。

• 时间维指针
• 排序与移动
• 复杂度 O(n^(5/3))

带修改莫队引入时间指针 Time 表示处理到第几次修改。查询按 (L 所在块, R 所在块, Time) 排序，块大小取 n^(2/3)，总块数 n^(1/3)。移动时三指针分别调整：L、R 在 [l,r] 区间内增删元素，Time 前进/后退时应用或回滚修改。总复杂度 O(n^(5/3))。

增加时间维后，块大小由 √n 调整为 n^(2/3)，以在 L、R、Time 三个维度间平衡移动量。修改操作需支持"前进/回退"，即能应用和撤销一次修改。复杂度从 O(n√n) 升到 O(n^(5/3))，是空间换时间的经典权衡。

• 增删代价不对称
• 莫队对增删均要求 O(1)
• 适用性讨论

莫队假设增删操作 O(1)（或接近 O(1)）。若添加与删除代价不对称（如删除无法 O(1)、或删除代价远高于添加），莫队可能不适用。此时可用"只加不减"的莫队变体（如带修改的扩展、或"回滚莫队"），或改用"只含添加的莫队"（利用分块回滚使删除只发生在小块）。若删除代价过高，可设计回滚莫队避免频繁删除。

经典莫队需要增删都 O(1)。当删除代价高时，回滚莫队固定"只做添加、删除时回滚到某状态"，使每次操作均为添加，规避删除瓶颈。若增删不对称且无法规避，需换算法（如分块扫描）。因此"是否适用"取决于能否把删除代价降到 O(1) 或规避。

• 空间为 O(n log n)
• 历史版本不易回收
• 垃圾回收考量

持久化保留所有历史版本，每个版本新增 O(log n) 节点，n 个版本空间 O(n log n)，比普通结构多用 O(log n) 因子。由于节点被多个版本共享，无法简单释放（旧版本可能仍在使用），垃圾回收或内存管理需追踪引用计数或使用可达性分析，避免回收仍被引用的节点。在竞赛中需注意内存上限。

持久化的空间代价是"保留历史"的必然结果：共享使节点生命周期跨越多个版本，回收困难。需权衡：若版本数多，空间可能吃紧；可用"版本差"、定期重建或只保留必要版本。垃圾回收需引用计数或惰性释放。

• metric TSP 的性质
• MST 与最优哈密顿回路的关系
• 翻倍算法与欧拉回路

对满足三角不等式（metric）的 TSP：先求最小生成树（MST），其权值 ≤ OPT（因最优哈密顿回路删一条边是生成树，故 MST ≤ OPT）。把 MST 的每条边复制一份（翻倍），得到欧拉图，必有欧拉回路。沿欧拉回路遍历，跳过已访问顶点（用三角不等式缩短），得到哈密顿回路，其权值 ≤ 2·MST ≤ 2·OPT。故 2-近似。

关键两步：MST 权值 ≤ OPT（下界），三角不等式允许"跳过"重复顶点而不增权。翻倍使欧拉回路权值 ≤ 2·MST，跳跃后 ≤ 2·OPT。这是 metric TSP 最简单 2-近似，Christofides 算法改进到 3/2。

• 欧拉序（入出序列）
• 路径到区间的映射
• 奇偶出现次数处理

树上莫队用"欧拉入出序"：DFS 时每个节点在进入和离开时各记录一次，得到长度 2n 的序列。对路径 (u,v)，根据 LCA 是否为 u 或 v 构造对应区间 [in[u], in[v]]（或 [out[u], in[v]]），区间内出现奇数次的节点即为路径上的节点（LCA 需特殊处理）。莫队在区间上移动，用"出现奇偶次数"维护路径节点集合。

技巧是把"路径上的节点"编码为"区间内出现奇数次的节点"：入出序中路径节点恰好出现奇数次（除 LCA）。莫队维护每个节点出现次数奇偶，统计奇数次节点。复杂度 O((n+q)√n)。

• 接受概率 exp(-ΔE/T)
• 高温时接受
• 跳出局部最优

模拟退火在每次迭代中生成邻居解，若邻居更优则接受；若更差，则以概率 exp(-ΔE/T) 接受（ΔE 为代价增量，T 为温度）。高温时该概率高，允许接受较差的解，从而有机会跳出局部最优去探索其他区域；低温时概率低，趋于收敛。通过渐降温度，实现"先探索后利用"。

关键是以"概率接受劣解"打破爬山法的确定性贪心局限，避免卡在局部最优。接受概率随温度下降而减小，使算法前期能跳出局部最优、后期稳定收敛。参数（初始温度、降温速率）影响探索与利用平衡。

• 线段树合并
• 子树信息聚合
• 复杂度 O(n log n)

每个节点维护一棵值域线段树（动态开点），表示子树内某种信息（如各值出现次数）。DFS 时，把子节点的线段树合并到父节点，用 merge 函数递归合并两个节点的对应区间，共享相同节点。合并后父节点线段树即子树统计。总复杂度 O(n log n)（每个节点只会被合并常数次）。

线段树合并把"自底向上聚合子树信息"做到 O(n log n)：每个节点线段树只建一次，合并时共享重叠部分。常用于求子树众数、子树内不同值个数、子树第 K 大等。空间 O(n log n)。

• 范围更新
• 懒标记下推
• 避免 O(n) 更新

线段树若对区间 [l,r] 的每个元素逐一更新，需 O(n)，无法支持高效范围更新。懒标记把"整个区间统一加 v"的标记挂在节点上，不立即下推到叶子，查询时再下推。这样一次范围更新 O(log n)，查询 O(log n)，总复杂度 O((n+q) log n)。懒标记是区间更新、区间查询（如区间加、区间赋值）高效的关键。

懒标记延迟更新，把"整段修改"合并为 O(1) 的标记，只在需要访问子节点时下推。这避免了逐元素更新，从而支持区间加、区间乘、区间赋值对。没有懒标记，范围更新退化为 O(n)。

• 离线条件
• 可加减维护
• 统计类问题

莫队适合处理"离线、可加减维护"的区间统计问题：所有查询预先给出（离线），且区间信息能通过"添加/删除一个元素 O(1)"维护（如区间和、出现次数、众数、异或）。若信息不可增量维护（如区间最大值位置难以 O(1) 增删）或必须在线，则莫队不适用。莫队把 O(nq) 的暴力降到 O((n+q)√n)。

适用条件是"离线"（需先排序）与"可加减"（增删 O(1) 维护答案）。统计类问题（频数、计数、异或）天然满足。不可维护或在线的问题（如实时查询、需复杂合并）需换算法。理解适用边界很重要。

• 误差预算概念
• 近似算法的近似比
• 量化的精度损失

近似算法用"近似比"量化解与最优解的误差，即"允许多少误差以换取速度"；机器学习推理的量化（如 int8 量化）用"误差预算"表示允许的精度损失，以换取更小的模型、更快推理。两者都是一种"在误差与效率之间权衡"的设计：给定误差预算（近似比/量化精度），选择最快的实现。它们共享"误差-复杂度交换"的思想。

类比核心是"误差预算"：一旦设定可接受误差上界，就能在算法/系统层面选择最快方案。近似算法通过近似比控制误差，量化通过位宽控制精度。两者都承认"不求绝对精确，但求误差可控且效率高"。

• set 存区间 [l,r,val]
• split 分裂
• assign 合并（推平）

ODT 用有序 set（或 map）存储区间，每个元素表示 [l, r] 且值为 val 的连续段。split(pos) 把包含 pos 的区间 [l,r] 分裂成 [l,pos-1] 和 [pos,r]，返回指向 pos 起点的区间。assign(l,r,v) 先 split(r+1) 和 split(l)，删除 [l,r] 内所有区间，再插入一个 [l,r,v] 区间，实现"推平"。操作基于 set 的平衡树，O(log 段数)。

split 是基础操作，assign 是核心（推平）。assign 通过 split 定位边界后删除并合并，使区间数减少，是 ODT 高效的关键。ODT 的复杂度取决于 assign 操作：大量区间赋值时区间数下降，效率高。

• ODT 复杂度依赖区间数
• assign 减少区间数
• 无 assign 时退化

ODT 的复杂度取决于 set 中区间段的数量。assign（推平）会合并大量小区间为一个大区间，显著减少区间数，使后续操作 O(log 段数)。若数据变化频繁（随机操作）或几乎没有区间赋值，区间段数会不断增长甚至接近 n，每次操作退化为 O(n)，整体 O(nq) 或更差。因此 ODT 仅在"大量区间赋值"（assign 频繁）的数据下高效。

ODT 本质是"用区间赋值减少区间数"的均摊结构。若 assign 少，区间数不下降，操作退化为线性。它不是通用数据结构，仅适用于"区间赋值 + 随机查询"类题目，且需注意构造数据可能卡到退化。这是其适用边界的核心。

• 段（区间）表示
• assign 推平
• 段信息维护

珂朵莉树把数组表示成若干连续同值段，用平衡树（set）维护。核心操作 assign(l,r,v)（区间推平）把 [l,r] 内所有段合并为一段 [l,r,v]，通过 split 定位边界后删除并插入。推平减少了段数，使后续操作高效。段内维护值与其他信息，基于"段"进行区间加、区间第 K 小、区间幂和等操作。

思想是"用段压缩表示"：同值连续段合并为一段，区间操作在段级进行。推平（assign）是让段数收敛的关键操作。配合 split 可拆分任意位置。ODT 适合"大量区间赋值"场景，用段维维护信息。