# 1. 前缀和与差分的对比应用中前缀和 O(1) 查询区间和但修改 O(n)，差分 O(1) 区间加但查询 O(n)，两者如何与树状数组结合？ A 前缀和修改单点为 O(1)，查询区间和为 O(n) B 树状数组无法同时支持区间加与区间查询 C 差分区间加为 O(1)，但单点查询需 O(n) ✓ 正确答案 D 差分与前缀和能同时做到查询和修改都 O(1)
# 2. 前缀和的差分还原中给定差分数组如何恢复原数组，区间加如何用差分优化？ A 区间 [l,r] 加 v 对应差分 d[l]+=v、d[l-1]-=v B 差分数组无法还原原数组 C 原数组可由差分数组逐项累加（前缀和）还原 ✓ 正确答案 D 区间加用差分需要 O(n) 时间
# 3. 二阶差分中等差数列区间加如何用两次差分后两次前缀和还原，与普通区间加在标记点上的差异 A 等差数列区间加只需一阶差分即可处理 B 二阶差分无法还原原数组 C 二阶差分的标记点数量与普通差分相同 D 二阶差分用两次差分打标记、两次前缀和还原，可处理等差数列区间加 ✓ 正确答案
# 4. 二维差分中矩形区域整体加 v 如何在四个角做 O(1) 标记、再经二维前缀和还原出完整矩阵 A 二维差分还原只需要一次一维前缀和 B 二维差分需要把矩形内每个点都加 v，复杂度 O(面积) C 矩形整体加 v 只需在矩形四个角做 O(1) 标记 ✓ 正确答案 D 二维差分只能处理一维区间
# 5. 树上差分的标记规则中为什么路径点差分在 u、v 处 +1、LCA 处 -1、LCA 的父节点再 -1，边差分与点差分有何不同？ A 树上差分无法统计路径覆盖次数 B 边差分需要额外在 LCA 父节点处 -1 C 点差分与边差分的标记方式完全相同 D 路径点差分在 u、v 处 +1、LCA 处 -1、LCA 父节点再 -1 ✓ 正确答案
# 6. LZW 压缩的最坏退化中重复性差的输入会使码本增长失控、压缩率劣于固定编码，字典满时的清空/固定策略如何处理？ A LZW 字典永不增长，码本固定 B 重复性差的输入使字典增长失控，压缩率可能劣于固定编码 ✓ 正确答案 C 字典满时只能清空，无法固定 D LZW 对任何输入都保证压缩
# 7. 逆 BWT 的 LF-mapping 原理中为什么用 Last 列的字符计数与 rank 查询就能逐字符还原原串，与前缀和/计数排序思想的关系？ A LF-mapping 用字符计数（前缀和）与 rank 定位，本质是计数排序/桶索引思想 ✓ 正确答案 B LF-mapping 与排序无关 C 逆 BWT 无法还原原串，只能还原排序 D 逆 BWT 只需要 Last 列，无需字符计数
# 8. 前缀异或与区间查询中如何用前缀异或数组 O(1) 求任意区间异或？ A 前缀异或利用异或没有自反性这一性质 B 区间异或需要 O(r-l) 时间 C 前缀异或无法求区间异或 D 区间 [l,r] 异或 = pre[r] ^ pre[l-1]，预处理 O(n)、查询 O(1) ✓ 正确答案
# 9. 前缀异或的应用中给定数组求最大异或子段，如何用前缀异或加 01-Trie 在 O(n log A) 内完成？ A 01-Trie 查询复杂度是 O(n) B 最大异或子段只能暴力枚举，O(n²) C 前缀异或无法用于异或最大值问题 D 用前缀异或把子段转为前缀对，再用 01-Trie 逐位贪心，总复杂度 O(n log A) ✓ 正确答案
# 10. 前缀差分/前缀和的扩展中二维前缀和、树上差分在区间统计问题中的应用？ A 树上差分无法统计路径覆盖 B 二维前缀和只能处理一维区间 C 二维前缀和可 O(1) 求任意矩形和，树上差分可处理路径覆盖统计 ✓ 正确答案 D 二维前缀和查询需要 O(n) 时间
# 11. LZ77 滑窗与 LZ78/LZW 字典的对比中指针引用 vs 字典码的编解码方式与流式特性差异 A LZ77 用滑窗指针（距离+长度）引用，LZW 用字典码字编码 ✓ 正确答案 B LZ77 与 LZW 都只用字典码 C LZ77 的窗口可以无限大，无内存限制 D LZW 解码不需要重建字典
# 12. AC 自动机上的模式计数中为什么文本扫描只需在节点上计数，再用 fail 树子树求和（差分）即可得到每个模式的出现次数？ A 节点计数无法用于模式统计 B 每个模式出现次数需重新扫描文本才能得到 C 子树求和与 fail 树无关 D 扫描时在节点计数，再用 fail 树子树求和得到每个模式出现次数 ✓ 正确答案
# 13. 集合覆盖贪心 ln n 近似比的证明中每次选覆盖最多未覆盖元素的集合，用调和级数 H(n) 界定近似比 A 集合覆盖贪心是最优的，近似比为 1 B 每步至少覆盖剩余未覆盖元素的 1/OPT 比例，近似比 ≤ H(n) ≈ ln n ✓ 正确答案 C 调和级数 H(n) 与近似比无关 D 贪心集合并无法保证任何近似比
# 14. 字典树的应用中自动补全、最大异或对（插入+逐位贪心）与 AC 自动机的关系？ A Trie 只能做完全匹配，不能前缀匹配 B Trie 支持自动补全、01-Trie 求最大异或对，也是 AC 自动机的基础 ✓ 正确答案 C AC 自动机与 Trie 无关 D 01-Trie 无法求最大异或对
# 15. 字典树的工程实现中为什么竞赛与生产常用静态数组（next[N][26]）代替指针节点，空间与缓存上的差异？ A 静态数组 next[N][26] 连续内存、缓存友好、避免 GC，适合小字符集 ✓ 正确答案 B 静态数组比指针实现占用内存更少且支持任意大字符集 C 指针节点实现缓存更友好 D 静态数组无法表示 Trie 结构
# 16. 迭代加深（IDA*）的复杂度中为什么每轮加深会重复搜索前几层，但在分支因子 b 较大时总代价仍是首层搜索的约 b/(b-1) 倍？ A 重复搜索使总代价是深度的指数中最大的 B IDA* 每轮不重复搜索，只搜索新层 C 分支因子 b 大时，重复搜索浅层的额外开销可忽略，总代价约为首层搜索的 b/(b-1) 倍 ✓ 正确答案 D IDA* 总代价与分支因子无关
# 17. 字典树（Trie）的插入/查询/前缀统计，与哈希表相比在"前缀匹配"场景的优势？ A 哈希表比 Trie 更适合前缀自动补全 B Trie 天然支持前缀匹配与前缀统计，哈希表难以高效处理前缀查询 ✓ 正确答案 C Trie 无法做前缀统计 D Trie 与哈希表在任意场景下能力相同
# 18. 近似比下界与 PCP 定理中 MAX-3SAT 不存在 (7/8+ε)-近似除非 P=NP，PCP 定理如何推出不可近似性 A MAX-3SAT 存在任意精度的近似算法 B 除非 P=NP，不存在 (7/8+ε)-近似算法，该下界由 PCP 定理推出 ✓ 正确答案 C PCP 定理与近似算法无关 D 随机赋值不能给出 7/8 近似
# 19. 字典树的变体中 01-Trie 求最大异或对与可持续化 Trie 的历史版本？ A 01-Trie 只能做字符串匹配 B 01-Trie 用逐位贪心求最大异或对，可持久化 Trie 用路径复制支持历史版本 ✓ 正确答案 C 01-Trie 无法求异或极值 D 可持久化 Trie 每次插入都复制整棵树
# 20. 字符频次前缀数组中预处理每种字符出现次数前缀后如何 O(1) 判断任意子串的字母构成与异位词关系 A 判断异位词需要 O(n) 重新统计 B 频次前缀数组无法判断子串字母构成 C 用前缀差 O(1) 得到任意子串频次向量，可判断异位词 ✓ 正确答案 D 频次前缀数组只能统计单个字符
