OI-wiki 中的 Garsia–Wachs 算法线性时间构建最优二叉查找树与字母序霍夫曼码的完整指南【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wikiGarsia–Wachs 算法是计算领域内用于在近线性时间$O(n\log n)$内构建最优二叉查找树与字母序霍夫曼码alphabetical Huffman code的高效算法由 Adriano Garsia 与 Michelle L. Wachs 于 1977 年提出。本文以 OI-wiki 仓库中的 docs/misc/garsia-wachs.md 为骨架结合 docs/dp/interval.md 等仓库内相邻资料系统讲解该算法的数学模型、三阶段流程、标志值哨兵技巧与复杂度分析并完整覆盖 POJ 1738 与 AtCoder DP-N 两道经典例题的实战思路帮助读者在石子合并类大范围$n$ 达 50000问题时摆脱区间 DP 的 $O(n^3)$ 困境。算法简介从 1977 到竞赛考场Garsia–Wachs 算法Garsia–Wachs Algorithm以 Adriano Garsia 和 Michelle L. Wachs 的名字命名他们于 1977 年发表了相关论文该算法用于在线性时间配合平衡树实现时总复杂度为 $O(n\log n)$内构建最优二叉查找树和字母霍夫曼码。在 OI / ICPC 竞赛语境中该算法最广为人知的应用是解决相邻石子合并的最小代价问题即石子合并的链式版本。这类问题用经典区间 DP 求解的复杂度为 $O(n^3)$详见仓库内 docs/dp/interval.md 中的区间 DP 讲解当 $n$ 达到 $50000$ 级别时完全不可行而 Garsia–Wachs 算法将复杂度降至 $O(n\log n)$是这类问题的标准高效解法。问题描述最优二叉查找树与字母霍夫曼码的统一模型给定一个整数 $n$以及 $n1$ 个非负权值 $w_{0},w_{1},\dots ,w_{n}$我们需要构造一棵有根二叉树要求该树有 $n$ 个内部节点且每个内部节点都有两个子节点——这意味着这棵二叉树恰好有 $n1$ 个叶节点我们将 $n1$ 个输入权值与二叉树的叶节点顺序一一映射目标是在所有具有 $n$ 个内部节点的可能树结构中找到一棵使外部路径长度加权和最小的树即最小化 $\sum_{i} w_i \cdot d_i$其中 $d_i$ 是根到第 $i$ 个叶子的路径长度。这个抽象问题在两种经典场景下落地最优二叉查找树当把这 $n1$ 个权值看作 $n$ 个有序键将搜索空间划分出的 $n1$ 个区间时问题转化为构造一棵二叉查找树使得搜索树中不存在值的平均代价最小。具体地每个区间的权值可视为搜索值落入该区间的概率外部路径长度的加权和直接决定了查找的期望时间。这正是最优二叉查找树optimal binary search tree问题的一个变体——注意这里的模型与常规以键为节点的 BST 不同它面向的是区间查询。字母霍夫曼码该模型同样可用于构造霍夫曼码用二进制值的可变长度序列无歧义地编码 $n1$ 个给定值。在这种解释中每个值的代码由从树根到对应叶子路径上的左步 / 右步序列给出例如左记为 $0$右记为 $1$。与标准霍夫曼码的关键区别在于以这种方式构造出的霍夫曼码是按字母顺序排列的alphabetical即这些二进制码的字典序与值的输入顺序完全一致。若一个值的权重代表它在编码消息中出现的频率则 Garsia–Wachs 算法的输出就是将消息长度压缩到最短的、且保持字母序的霍夫曼代码。这一性质使其在需要同时满足前缀编码与保序编码的场景如按字典序排列的符号表压缩中不可替代。算法三阶段流程Garsia–Wachs 算法一般包括三个阶段构建阶段构建一棵值位于叶子的二叉树注意此时叶子顺序可能错误距离计算阶段计算树中根到每个叶子的距离重构阶段构建另一棵二叉树叶子的距离与阶段 2 相同但顺序正确。如上图所示在算法的第一阶段通过查找合并输入序列的无序三元组构建的二叉树左侧和算法输出的正确排序的二叉树右侧两者的叶子高度保持一致。这张示意图位于仓库的 docs/misc/images/garsia-wachs.png清晰地展示了先构造无序树 → 再重排为有序树的核心思想。标志值Sentinel技巧如果输入在序列的开始和结束处增加两个标记值 $\infty$或任何足够大的有限值则算法的第一阶段更容易描述。所以在竞赛题解中使用 Garsia–Wachs 算法时对于一个长度为 $n$ 的数组 $\mathit{num}$我们一般定义$$ \mathit{num}[0] \mathit{num}[n1] \infty $$标志值的作用有两个方面其一序列结尾的标志值大于之前的任意两个有限值保证总能找到满足条件的三元组其二左端的标志值保证总能找到重新插入新节点的位置。这一技巧在 docs/misc/garsia-wachs.md 中被明确强调是竞赛实现中必不可少的一步。第一阶段合并与重插入第一阶段维护了一个森林森林中最初由为每个非标志输入权重创建的、由单节点组成的树构成。每棵树都与一个值相关联该值等于其叶子权重之和初始即输入权重本身非标志输入权重构成一个树节点。为了维护这些值的序列序列两端各放置一个标志值。初始序列就是叶权重的输入顺序。随后重复执行以下步骤每一步都减少输入序列的长度直到只剩一棵包含所有叶子的树查找三元组在序列中找到前三个连续的权重值 $x$$y$$z$使得 $x \leq z$。因为序列结尾的标志值大于之前的任意两个有限值所以总是存在这样的三元组合并从序列中移除 $x$ 和 $y$并创建一个新的树节点作为 $x$ 和 $y$ 节点的父节点值为 $xy$重插入在原来 $x$ 的位置以前、大于或等于 $xy$ 且距 $x$ 最近的值的右边重新插入新节点。因为左标志值的存在所以总是存在这样的位置。高效实现平衡树维护序列为了高效实现第一阶段该算法可以在任何平衡二叉查找树结构中维护当前值序列。这样的结构允许我们在对数时间内完成两件事移除 $x$ 和 $y$以及重新插入它们的新父节点 $xy$。此处蕴含两个关键的单调性事实是复杂度分析的核心在每一步中数组中位于偶数索引上直到 $y$ 值的权重形成了一个递减序列位于奇数索引位的权重形成另一个递减序列。因此重新插入 $xy$ 的位置可以通过对这两个递减序列使用平衡树执行两次二分查找、在对数时间内找到。同时通过从前一个三元组的 $z$ 值开始的线性顺序搜索可以在总线性时间复杂度内完成对满足 $x \leq z$ 的第一个位置的搜索。第二、三阶段与总复杂度Garsia–Wachs 算法的第三阶段的证明——即存在另一棵具有相同距离的树并且这棵树提供了问题的最优解——是很重要的。但由于其证明方式有多种且过于复杂此处略去感兴趣的读者可参考文末的参考文献。在第三阶段为正确的前提下第二和第三阶段很容易在线性时间内实现。因此在长度为 $n$ 的输入序列上Garsia–Wachs 算法的总时间复杂度为 $O(n\log n)$。与区间 DP 的对比何时使用 Garsia–Wachs仓库中的 docs/dp/interval.md 对区间类动态规划做了完整讲解令状态 $f(i,j)$ 表示将下标位置 $i$ 到 $j$ 的所有元素合并能获得的价值的最大值则$$ f(i,j)\max{f(i,k)f(k1,j)cost} $$其中 $cost$ 为将这两组元素合并起来的价值。区间 DP 适用于 $n$ 较小一般 $n \leq 1000$的情况当 $n$ 达到 $10^4$~$10^5$ 级别时$O(n^3)$ 或优化后的 $O(n^2)$ 都无法承受此时 Garsia–Wachs 的 $O(n\log n)$ 成为唯一可行的选择。两者适用范围的区别值得注意区间 DP 可以灵活处理求最大值与环形排列等变体见 docs/dp/interval.md 中关于环的处理方法而 Garsia–Wachs 算法面向的是链式、求最小值的相邻合并问题且其正确性依赖特定的单调结构。应用与生态函数式编程语言 Haskell 的garsia-wachs package对 Garsia–Wachs 算法做了函数式实现。它主要用于两个场景构建最佳搜索表以最优复杂度平衡rope数据结构。注释rope是 Haskell 语言中用于操作带有可选注释的字节串bytestring的手指树工具即仓库 docs/ds/finger-tree.md 中讲解的手指树finger tree数据结构。手指树是一种支持高效前缀/后缀操作与合并的持久化序列结构与 Garsia–Wachs 算法配合可以以最优复杂度维持 rope 的平衡性。例题精讲POJ 1738 An old Stone Game有一个古老的石头游戏。在游戏开始时玩家将 $n$$1 \leq n \leq 50000$堆石头排成一行。目标是将石头合并成一堆规则如下在游戏的每一步玩家可以将相邻的两个堆合并成一个新的堆。分数是新堆的石头总数。请计算总分中的最小值。解题思路石子合并的题目很经典一般可以用区间 DP 解答但是当数据量很大例如此题中的 $n$$1 \leq n \leq 50000$时用 Garsia–Wachs 算法求解更高效初始化建立一个大小为 $n$ 的数组 $\mathit{num}[n]$其中 $\mathit{num}[0] \mathit{num}[n1] \infty$反复合并每次找到一个最小的 $i$使 $\mathit{num}[i-1] \leq \mathit{num}[i1]$并将 $\mathit{num}[i-1]$、$\mathit{num}[i]$ 合并为 $\mathit{temp}$再找到前面一个最大的 $j$使得 $\mathit{num}[j] \mathit{temp}$将 $\mathit{temp}$ 移到 $j$ 后面终止条件重复上一步直到剩余堆数为 $1$。关于每次只能合并相邻石子堆要求的证明因为 $\mathit{num}[j] \geq \mathit{num}[i-1] \mathit{num}[i]$我们可以将 $\mathit{num}[j1]$ 到 $\mathit{num}[i-2]$ 看成一个 $\mathit{num}[mid]$ 的整体所以一定是先合并 $\mathit{sum}$即先合并 $\mathit{num}[i-1]$ 与 $\mathit{num}[i]$ 这两个相邻堆因此没有违背题目要求。这一论证保证了算法先合并再后移的操作与只能相邻合并的约束相容。ATCODER DP N Slimes$N$ 个史莱姆排成一排。最初左边第 $i$ 个史莱姆的大小为 $a_{i}$。Taro 试图将所有史莱姆组合成一个更大的史莱姆。他会反复执行以下操作直到只有一个史莱姆选择两个相邻的史莱姆并将它们组合成一个新的史莱姆。新的史莱姆的大小为 $xy$其中 $x$ 和 $y$ 是组合之前史莱姆的大小。这一步骤产生 $xy$ 的成本。合成史莱姆时史莱姆的位置关系不会改变。找出可能发生的最小总成本。这是石子合并问题在 AtCoder DP 系列中的同构变体大小对应石子数成本 $xy$对应新堆石子总数同样要求最小化相邻合并的总成本。由于 $N$ 可达 $10^5$ 级别该题约束下区间 DP 不可行直接套用 Garsia–Wachs 的三步流程即可初始化序列两端为 $\infty$反复寻找满足 $\mathit{num}[i-1] \leq \mathit{num}[i1]$ 的最小 $i$ 并合并、回插直至只剩一个节点。两道例题共同说明Garsia–Wachs 算法是链式相邻合并最小代价类问题的通用高效解法与题目背景石子、史莱姆、木头等无关。参考资料与拓展阅读Garsia–Wachs algorithm维基百科词条提供算法历史与数学背景Data.Algorithm.GarsiaWachsHaskell garsia-wachs 包文档garsia-wachs: A Functional Implementation of the Garsia-Wachs Algorithm函数式实现的完整源码Sentinel value维基百科词条解释标志值/哨兵值的通用概念A new proof of the Garsia-Wachs algorithm该算法新证明的学术论文。延伸阅读仓库内若想系统理解该算法的前驱知识可继续阅读 docs/dp/interval.md区间 DP 的完整讲解与 docs/ds/finger-tree.md手指树数据结构。OI-wiki 将 Garsia–Wachs 算法归入 docs/misc/index.md 所描述的难以分类的算法及 OI 相关知识板块但正如本文所示它在石子合并、最优二叉查找树与字母序霍夫曼码三个方向上都拥有明确且重要的实战价值。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考