位并行、Bitset DP 与 Cartesian Tree

• 单调栈维护右链的构造流程
• 弹栈节点挂为新元素左子树
• 中序保下标、堆序保值的双不变量

用单调栈 O(n) 构造大根笛卡尔树：从左到右扫描数组，维护一个栈（栈内节点构成当前树的右链，值严格递减）。处理新元素 x 时，不断弹出栈顶值小于 x 的节点，最后一个被弹出的节点作为 x 的左子树根；若弹出后栈不空，x 作为新栈顶的右孩子；若栈空，x 成为新根。每个节点入栈出栈各一次，总复杂度 O(n)。

正确性依据：栈内右链始终保持两个不变量——中序遍历即数组顺序（左子树在前、根、右子树在后），堆序即值序（父值 ≥ 子值）。弹出操作把右链上较小者挂到 x 的左子树，恰好同时维持这两个不变量。该构造是 RMQ→LCA、直方图最大矩形等问题的公共前置步骤。

单调栈构造的实质是"维护右链 + 弹栈挂左子树"，与"找最近更大/更小元素"的单调栈用法一脉相承，区别在于这里要建立树形结构；面试时手推一个小例子（如 [3,2,1,4]）即可讲清全流程。

• 小根笛卡尔树中子树区间即"该高度为最小值"的区间
• 面积 a[u]×size(u) 枚举所有候选
• 与单调栈"左右最近更小"解法的对应

直方图最大矩形与笛卡尔树的关系：以小根堆序建笛卡尔树（值小的在上），每个节点 u 的子树对应数组中的一段连续区间，且区间内所有值 ≥ a[u]，a[u] 恰是该区间的最小值——因为中序保下标连续、堆序保"根是子树最小值"。以 a[u] 为高的最大矩形面积 = a[u]×size(u)（子树大小即区间宽度），全局答案 = 所有节点取 max，单调栈构造后一次 DFS 统计子树大小即可，总 O(n)。

该关系与经典"单调栈求每个位置左右第一个更小位置"的解法等价：左右边界由最近更小元素确定，宽度 = 右边界-左边界-1；笛卡尔树把这一过程显式化为树结构——每个节点的"影响区间"正是左右最近更小元素夹出的范围。实现时可在数组两端补哨兵（如 -1）简化边界处理。

把"每根柱子作为最低点能向两侧扩展多远"编码进子树区间，是笛卡尔树几何意义的直接应用；面试先讲单调栈 O(n) 解，再点出与笛卡尔树的对应关系更能体现深度。

• 移位 + 按位或的向量化转移
• 可达性/存在性 DP 的适用条件
• 计数、路径回溯、浮点容量的退化情形

0/1 背包可达性问题（是否存在子集和为 w）可用 bitset 优化：维护位集 dp，第 i 位为 1 表示"和为 i 可达"，对重量 w 的物品转移为 dp |= dp<<w，每条转移 O(W/64)（W 为容量），n 件物品总复杂度 O(nW/64)，相比布尔数组 DP 的 O(nW) 提速约 64 倍。适合的结构：纯可达/可行性判断、连通性、存在性判定；配合按余数分桶移位还可处理"按模分组"的变体背包。

何时退化：需要方案计数、方案字典序、恰好装 k 件或回溯具体方案时，bitset 只保存布尔可达性，无法记录计数与路径（除非额外构造辅助结构）；容量为浮点或 W 极大而 n 很小时，位集长度浪费；多重背包用单调队列优化在物品种类少、W 大时可能更优。

bitset 背包把"加和转移"变成"移位 + 或"的向量运算，利用机器字并行；面试答出退化情形（计数、路径、依赖顺序）即可体现工程判断，这是区分"会用"与"懂原理"的点。

• 对角线方向的位向量组织
• P（插入/删除）与 M（匹配/替换）的转移
• d 很小时的复杂度优势

Myers 的 O(nd/w) 位并行编辑距离把 Levenshtein 计算按"对角线"组织：维护两条位向量 P 与 M（分别编码插入/删除与匹配/替换的等价信息）以及每个字符的匹配位掩码 Peq[c]，用移位、与、或等整字位运算模拟整条对角线的递推，每次迭代处理一条对角线，d 为编辑距离、w 为机器字长。当 d 很小（如文本近似匹配）时 O(nd/w) 远优于 O(nm)。

实现要点：滚动位向量表示当前对角线的前沿位置，插入/删除通过 P、M 的位移与补丁位（HP/HR 进位）交互，匹配通过 Peq[ch] 与位移后的向量按位与；相比普通 DP 的逐单元递推，位并行一次推进 w 个单元，代价是只能得到距离值，重建编辑路径需额外记录回溯信息。

位并行把 DP 矩阵按对角切片、用整字运算同时算 w 个单元，是"数据并行换语言级常数"的典范；面试答出 P/M 向量与 Peq 掩码、以及复杂度 O(nd/w) 中 d 的含义即算掌握。

• 平衡树组织字符串与 split/concat 操作
• splay 势能分析给出均摊 O(log n)
• 与"逐字节拼接"的本质区别

Rope（绳）用二叉树表示长字符串，叶子存片段、内部节点存子树总长度；拼接 s1+s2 即把两棵 splay 树 concat 成一个新根节点，split 按长度二分。splay 树版 rope 的每个操作（拼接、分裂、按位置取子串、插入删除）都归结为 splay 的 split/concat：拼接 = 两次 splay 定位 + 常数次指针修改，均摊 O(log n)。

复杂度证明：splay 树的势能分析给出任意 m 次操作的均摊 O(log n)——定义势能为所有节点秩（log 子树大小）之和，zig-zig/zig-zag/zig 三种旋转后势能变化被 splay 的摊销代价覆盖，因此 concat（含其触发的 splay）均摊 O(log n)；内存总量 O(字符串长度)，与逐字节拼接的 O(长度) 形成本质区别。

Rope 的卖点是把"O(长度) 的拼接"变成"O(log n) 的树重组"，本质是平衡树的区间操作；面试讲清"均摊 O(log n) 来自 splay 势能"即可，无需展开全部旋转细节。

• 子集枚举总量 O(3^n) 的下界
• SOS 高维前缀和与位向量化聚合的区别
• 斯坦纳树 dp[mask][v] 中的子集合并

经典子集枚举 O(3^n)：对每个集合 S 枚举其子集 T，总量 Σ2^|S| = 3^n；用 SOS（高维前缀和）可把"对每个 S 求 max/min over T⊆S of f[T]"降到 O(n·2^n)。bitset 的参与方式：当转移形如"某状态集合按位或/与/移位"时（如状态压缩 + 连通性判定），把状态压成位集用整字运算批量推进，常数除以 64。

斯坦纳树应用：dp[mask][v] 表示以 v 为根、连通 mask 中终点的最小代价；子集合并 dp[mask][v]=min(dp[T][v]+dp[mask\T][v]) 本质是 O(3^k) 枚举（k 为终点数），位集优化点在于对固定 v 的所有 mask 用位运算做"可合并对"的批量判定；但 min 聚合本身仍需普通循环，位集的收益只在转移可向量化为位运算时显著。

O(3^n) 枚举子集的下界是"对每个 S 遍历其子集"，bitset 只能加速可表达为位运算的聚合（按位或/与/移位）；回答需区分"枚举"与"向量化聚合"两件事，避免夸大 bitset 的适用范围。

• 64 位字数组存储与跨字搬移
• 移位先按字移动再处理边界位
• POPCNT 与 SIMD 向量化

std::bitset 内部是一个 64 位字（unsigned long long）数组，每字 w=64 位。移位操作先按字整体搬移（字节级 memmove），再处理跨字边界的位搬移：每个目标字 = 源字移位后的残留部分与相邻字移入部分按位或，复杂度 O(N/64)。按位与/或/异或按字循环，复杂度 O(N/64)；count 用 POPCNT 指令（x86 的 popcnt）逐字统计 O(N/64)；any 在遇到非零字时提前退出，或做 SIMD 归约。

SIMD 加速：AVX2 的 256 位向量一次处理 4 个字，count 可用 VPSADBW 等指令实现向量化 popcount；编译器对固定大小的 bitset 在 -O3 -march=native 下常自动向量化。bitset 各操作复杂度均为 O(N/64)，这是"常数 64 倍加速"的来源。

bitset 的本质是"机器字并行 + 少量跨字搬移"，各操作复杂度都挂 N/64；回答围绕字数组、跨字搬移、popcnt 三个层面即可，无需深入指令细节。

• 随机符号累加的线性估计器
• 4-wise 独立保证方差有界
• 多副本中位数放大成功率

AMS 算法估计流的二阶矩 F2=Σf_i²：对每个元素维护随机 4-wise 独立哈希 ξ(x)∈{±1}，累加 X=Σξ(x)（元素每出现一次加一次 ξ(x)），则 E[X²]=F2；4-wise 独立足以保证 Var(X²)≤2F2²（矩计算只涉及 4 次乘积的期望）。单次估计相对误差大，于是运行 t 个独立副本取中位数：由 Chebyshev 与 Chernoff 可得 O(log(1/δ)) 个副本后，相对误差超过 ε 的概率 ≤δ，总空间 O((1/ε²)·log(1/δ)) 个字。

4-wise 独立的用途：只需 X² 的期望与方差计算涉及 4 次乘积的独立性，4-wise 足以让方差有界，比完全随机哈希节省随机位数；这是"低阶独立哈希足够支撑矩估计"的代表性结论。

F2 估计是"线性投影 + 中位数放大"的模板：随机符号累加给出无偏估计、4-wise 界定方差、多副本中位数放大成功率；面试按这三步展开即完整，无需背诵完整证明。

• 中序保区间、堆序保最优的证明骨架
• RMQ→LCA 与 LCA→RMQ 的双向归约
• 与欧拉序 ±1 RMQ 的闭环

笛卡尔树是 RMQ 与 LCA 等价的桥梁：对数组构造中序为下标、堆序为值的笛卡尔树后，任意区间 [l,r] 的最值节点 = 节点 l 与 r 的 LCA（RMQ→LCA）；反过来任意树的 LCA 可用 Euler Tour 转为深度序列的 ±1 RMQ（LCA→RMQ）。两个方向都是 O(n) 构造，形成闭环。

证明核心：设 w=LCA(l,r)，由中序性 l、r 分居 w 的左右子树（或 w 即其一），故 w 的下标落在 [l,r] 内；由堆序性，w 的子树内值最优，且 w 子树的下标区间覆盖 [l,r]，故 w 是 [l,r] 的最值节点。反证方向：若某节点不是 l 与 r 的 LCA，则存在更优（更靠近根、值更优）的堆序祖先，矛盾。

桥梁证明的骨架是"中序保区间、堆序保最优"两条不变量；这也是静态 RMQ 转 LCA 题目的理论依据，面试可把两题合并记忆，先讲不变量再讲归约方向。

• 随机位置采样的期望等于最大频率
• 诚实（无偏）与方差大的矛盾
• 多副本中位数的 (ε,δ) 保证

AMS 对 F∞（最大元素频率）的诚实估计：均匀随机取一个流位置 j，统计 a[j] 在整个流中的总出现次数 c（实现上用"自 j 起的连续同值游程"或其变体），则 E[c]=F∞，即无偏（诚实）——无偏性来自对称性：最大频率元素在流中的每个出现位置被等概率选为样本起点，其期望贡献恰为 F∞ 乘以采样概率的倒数。

问题在方差：c 的方差可达 O(F∞·n) 量级，单次估计不可靠；解法仍是多副本 + 中位数（median trick），把 (ε,δ) 保证的空间压到 O((1/ε²)·log(1/δ)) 字。相比之下"有偏"的估计器（如用第 k 大频率代替最大频率）以系统性低估换取更小方差，需根据用途取舍——统计重尾分布时无偏优先，资源受限时接受轻微低估。

诚实性 = 期望正确，工程性 = 方差可控；AMS 系列的标准套路是"无偏基估计器 + 中位数放大"，本题考核对两个性质的区分，回答时把"无偏性证明"与"方差控制"分开讲。

• MG 的确定性绝对误差界
• CM 的概率相对误差界
• cardinality 高低时的选型差异

Misra-Gries（MG）用 k=1/ε 个计数器，给出确定性保证：对任一元素 x，估计值 f̂(x) ≥ f(x)-εn（绝对误差界）；当 distinct 元素多而各频率低时，计数器频繁被全体减一淘汰，估计质量随淘汰次数恶化。Count-Min（CM）用 d×w 计数矩阵 + d 个哈希，给出概率保证：误差 ≤ε||f||₁ 且失败率 ≤δ，空间 O((1/ε)·log(1/δ))。

基准结论：在少量热元素（heavy hitter 明显）且要求确定性界时 MG 更紧凑（仅 1/ε 个计数器）；在大量 distinct、需要点查询上界且允许小概率失败时 CM 更稳（log 因子换失败率），且 CM 支持范围查询、合并等衍生操作。cardinality 低时两者差距不大；cardinality 高时 MG 的误差随"被淘汰次数"线性恶化，CM 误差只与频率向量范数相关、与 distinct 数无关。

MG 是"确定性 + 绝对误差"，CM 是"随机化 + 相对误差 + 失败率"，选型取决于数据分布与错误模型；说出"MG 误差与 n 有关、CM 误差与频率范数有关"即抓住本质。

• 两种算法的计数器维护规则
• 相同的误差下界 f-εn
• 顶替继承最小值的势能论证

Space-Saving 与 Misra-Gries 在计数器数 K 相同（K=1/ε）时可互相模拟：MG 的"新元素出现时全体计数器减一、删掉零值计数器"，等价于 Space-Saving 的"新元素顶替最小计数器并把计数值 +1（继承被顶替者的最小值）"——两者都保证估计值 f̂(x) ≥ f(x)-n/(K+1)，且"前 K 名不漏报"。因此 K 计数器的 MG 与 SS 误差界相同，SS 只是把 decrement 换成增量继承，实现更简单且计数单调。

关键论证：每个计数器被顶替时至少继承此前最小值，累计"流失量"不超过 n/(K+1) 乘以总轮数；对任一元素，其估计 = 真实出现次数 - 被顶替期间的流失 ≥ f - n/(K+1)。这就是 heavy hitter 的 ε-approximate 下界系列的同一证明骨架。

等价变换的核心是"decrement 与继承最小值"在势能上等价；证明抓住"流失总量 ≤ n/(K+1)"即可，这与频率估计下界直接挂钩，面试答出"同一误差界、两种实现"即完整。

• 全体减一与"每次减一配对一次新出现"
• 流失总量 ≤ n/(K+1) 的封顶论证
• heavy hitter 不漏报的推论

Misra-Gries 维护 K 个计数器：新元素 x 若在表中则计数 +1；若不在且表满，则全部计数器 -1（并把归零的计数器清空），x 不入表；若表未满则直接加入。该过程保证：任一元素 x 的估计 f̂(x) ≥ f(x)-n/(K+1)。证明关键：把"全体减一"看成一次"删除 (K+1) 个出现记录"（x 的那次新出现 + K 个被减的计数），而每次这样的删除必然伴随一个新的元素出现，故删除总轮次 ×(K+1) ≤ n，x 被"错过"的次数 ≤ n/(K+1)。

推论：当 f(x) ≥ εn 且 K≈1/ε 时，f̂(x) ≥ f(x)-εn ≥ (1-ε)f(x)，即 heavy hitter 的估计保真、不漏报——这就是 (k-1)/k 频率下界的来源（k=K+1 时误差 n/k）。

下界证明的钥匙是"每轮全体减一与至少一个新出现元素配对"，从而把流失量用 n/(K+1) 封顶；这是计数草图最基本的确定性界，面试时写出配对论证即到位。

• Gap Buffer 的光标局部编辑优势
• Rope 的任意位置 O(log n) 编辑
• 缓存友好性与内存开销的对比

Gap Buffer 在字符数组中间保留一段空隙，插入/删除集中在 gap 附近 O(1) 均摊（挪 gap 的代价 O(移动距离)），适合"光标局部编辑"（如 Emacs 与现代编辑器的基础实现）；缺点是光标大跨度移动与分散编辑时反复 memmove，且无法高效拼接与撤销。Rope（源自 Xerox PARC 的 "Ropes: an Alternative to Strings"）用平衡树组织串，任意位置插入删除、拼接、取子串均 O(log n)，撤销可借助持久化结构天然支持，但节点指针内存开销大、缓存不友好，短文本下常数大。

取舍：短文本 + 光标局部编辑选 Gap Buffer（简单、缓存好、实现成熟）；长文本/大文档、频繁随机位置编辑与拼接、需要高效分片视图时选 Rope。可撤销与多版本场景下 Rope 配合持久化是 Gap Buffer 难以企及的。

两者是"连续内存局部编辑"与"树形结构全局操作"的代表；面试以"编辑模式 vs 复杂度需求"为轴对比即完整，若结合现代编辑器（如 piece table）做延伸更佳。

• 字符位掩码 B[c] 与状态位向量 D
• 每字符一步的转移公式
• 自动机状态集的字级并行

Shift-And 把模式 P[1..m] 编码成字符位掩码 B[c]（第 i 位为 1 当且仅当 P[i]=c），维护位向量 D：扫描文本每个字符 ch 时执行 D = ((D<<1)|1) & B[ch]，D 的第 i 位为 1 表示"当前以 ch 结尾、长度为 i 的后缀匹配 P 的前 i 个字符"。当 D & (1<<(m-1)) 非零时发现匹配，起点为 i-m+1。每字符 O(m/64)，m≤字长时 O(1)，总 O(n·m/64)。

Shift-Or 是等价变形（0/1 反转 + 或运算），常数更小。位向量语义：每次迭代等价于"KMP 自动机的状态集合"并行推进，全部状态压缩进一个机器字，是位并行精确匹配的教科书实现；模式变长时用多个字（每 64 位一段）维护。

D 是"前缀匹配状态集"的压缩表示，移位模拟"失配回退 + 推进"；把自动机状态集并行化是位并行算法的统一视角，面试写出转移公式即可。

• CM 只维护频率上界信息
• min/max/median 需要的序与极值信息
• 分位数草图与 CM 的问题域区别

Count-Min 只维护"每个元素的频率计数上界"，回答的是点查询（估计 f(x) 的上界）、heavy hitter 与基于计数的范围查询（前缀和近似）等问题；min/max 需要遍历值域或维护极值结构，median 需要元素的序信息（排序/分位数），这些信息在 CM 的计数矩阵中完全缺失。CM 的误差模型是"频率上的加性 ε||f||₁"，不是"数值/键值上的"，故无法回答数值型查询。

可行的替代：min/max 用区间维护结构或数值型草图；median/分位数用 GK、KLL、t-digest 等分位数草图。若 CM 硬做 min，只能先找出候选（如 top-k 频率）再回源验证，这不是草图的原生能力。选型时必须按查询类型匹配草图家族。

回答"为什么不能"的关键是指出 CM 的信息论盲区——没有存任何关于值的序/极值信息，只有计数；草图选型要按查询类型匹配，面试时点出"CM 回答计数类问题、GK/KLL 回答序类问题"即完整。

• UTF-8 变长编码与位掩码的冲突
• 掩码表规模与缓存问题
• AC 自动机与编码解耦的优势

位并行模式匹配（Shift-And/BNDM）假设模式短、字符单字编码、可预计算每字符位掩码。中英文混合文本是变长编码（UTF-8 中文 3 字节）：按字节处理会把多字节字符拆开产生伪匹配，按码点处理需先解码成固定宽度整数（破坏字节流），且中文字符集大，B[c] 掩码表随字符数线性膨胀、缓存不友好；位向量的 m 位长度对长中文模式也不够（需多字维护）。

AC 自动机把模式建进 trie + fail 链，一次扫描 O(n+匹配数)，复杂度与模式数、字符编码解耦——按字节流建树即可天然处理多字节字符；配合双数组/trie 压缩与 goto 表实现，在大模式集上远超位并行。因此位并行只在"模式短、字符集小、纯 ASCII"场景有优势。

位并行输在"编码假设"与"掩码表规模"，AC 赢在"字典树一次扫描、与编码无关"；回答落点在字符编码与掩码空间两个层面即完整。

• 只递增等于当前最小计数的桶
• 保持频率上界不变量的论证
• 一次 min 读取 + 条件写的实现成本

保守更新（conservative update）优化 Count-Min：插入元素 x 时不是把 d 个哈希桶全部 +1，而是先计算 min_j C[h_j(x)]，只把"等于该最小值"的桶 +1。这样任一时刻任一桶的计数值都等于"至少某个元素出现次数的下界"，显著减少过估计：点查询上界 f̂(x) ≤ f(x)+ε||f||₁ 仍然成立，但实际误差常远小于标准 CM（尤其是冷元素）。

工程实现：插入需要一次额外的 d 路读取（求 min）与一次条件写，代价是延迟略增、吞吐略降；收益在 heavy hitter 场景明显——标准 CM 中热元素使所有桶膨胀，保守更新让冷元素桶保持低位，点查询精度大幅提升。注意保守更新对范围查询、合并等依赖"桶内一致性"的操作需要偏置补偿或特殊处理。

核心洞察是"只让承载最小计数的桶增长"能遏制全局膨胀，同时保持上界不变量；面试讲清"min 读取 + 条件写"的流程即算掌握，不必纠结全部变体。

• 后缀自动机状态集的位向量
• 反向窗口扫描与位向量清空
• cut-the-rope 提前终止窗口

BNDM（Backward Nondeterministic Dawg Matching）把模式建为后缀自动机（Dawg）的位向量表示：维护一个位向量 D，从窗口末端向左扫描文本，每读一个字符更新 D（与 Shift-And 反向的转移），D 中的位表示"模式的后缀与当前位置向后的文本子串匹配"的集合；当代表模式首字符的位（最高位）置 1 时，窗口起点可能构成匹配，继续向左扩展验证，成功后窗口整体跳跃。

cut-the-rope trick：扫描过程中一旦位向量变为 0，说明当前窗口内不可能再有匹配，立即终止本窗口的扫描并右移窗口（"剪断绳子"），避免扫完整窗口；配合模式最右字符的跳过启发，平均可跳过大量字符。最坏 O(nm)，平均通常优于逐字符扫描，适合模式短、长文本的场景。

BNDM 是"反向窗口 + 位并行后缀自动机状态"；cut-the-rope 是其常数杀手锏——位向量归零即窗口无望，立即跳跃，面试答出"归零即剪断"即抓住要点。

• Warshall 按 k 迭代的中间点限制
• A[i] |= A[k] 的按位或实现
• 复杂度分析与正确性论证

传递闭包用 Floyd-Warshall 变体：按 k=1..n 迭代，若 i 可达 k（A[i][k]=1），则执行 A[i] |= A[k]（行向量按位或）。用 n 个 bitset 表示邻接矩阵的每一行，内层"对每个 i 检查并或上第 k 行"成为 O(n/64) 的整字操作，总复杂度从 O(n³) 降到 O(n³/64)。

正确性：Warshall 不变量——第 k 轮结束后 A[i][j]=1 当且仅当存在一条中间点只取自 {1..k} 的 i→j 路径；按位或恰好实现"i→k 的路径 + k→j 的路径"的合并，且 k 的迭代顺序保证中间点限制不变量成立。位集还可继续用分块 + 预处理"块内位或"（Four Russians 思想）把常数进一步压低，但 O(n³/64) 是标准结论。

位并行把"行与行之间的布尔合并"向量化；要点是 Warshall 按 k 迭代的顺序保证正确性，位或只优化内层、不改算法语义，面试时把这两点分开讲。