Introducing to the Huffman Tree
在《算法竞赛进阶指南中》，李煜东是这样描述哈夫曼问题的：
构造一棵包含 n 个子节点的 k 叉树，其中第 i 个叶子节点带有权值\(w_j\)，要求最小化\(\sum w_i*l_i\)，其中\(l_i\)表示第 i 个叶子节点到根节点的距离。
具体的哈夫曼树讲解请看：https://www.jianshu.com/p/95fba425be44
在《算法竞赛进阶指南中》，李煜东是这样描述哈夫曼问题的：
构造一棵包含 n 个子节点的 k 叉树，其中第 i 个叶子节点带有权值\(w_j\)，要求最小化\(\sum w_i*l_i\)，其中\(l_i\)表示第 i 个叶子节点到根节点的距离。
具体的哈夫曼树讲解请看：https://www.jianshu.com/p/95fba425be44
我们可以考虑使用线段树来维护区间的面积（对于一对不认识的人，可以在二维空间中用一个边为\(1\)的块来表示。这时我们的问题便转换成为在坐标系中某一范围内的面积（面积就是区间内认识的人数）。我们再进行研究，就会发现每一次操作一次区间，我们操作的图形在二维坐标系上就会表示成两个对点落在\(y=x\)这条直线上。我们首先给直线\(y=x\)上的点描黑（自己总会认识自己），然后写一个线段树。我们在合并两个区间的时候需要注意，如果合并时涉及到两个矩形重叠，那么我们需要取最高的值来表示矩形的上边缘。在区间内，上边缘的高度一定是单调递增的，所以我们可以二分出一个高度小于覆盖高度的偏移量，这样可以加速合并。具体请看代码：
这道题我们首先会不可避免地对每一个序列进行排序。每一个序列的顶部的和就是最大和，而次大和就是 \(n-1\)个序列的最大和 和 一个头部值最小的序列的头部值 之和。所以，我们把视野缩小一些，讨论两个序列的合并。
如何找到一对异或值最大的数字呢？我们先从二进制计算（位运算）本身讲起，如果我们要保证\(Xor\)值更大，那么我们就需要尽可能多的\(1\)，除此之外，\(1\)的位置也非常重要，在一些情况下靠前更好。我们可以考虑从最高位为起点向最低位建立一个 Trie 树。我们记\(num[i]\)表示第\(i\)位的\(0或1\)状态。建立 Trie 树之后，我们计算出每个数所对应的异或值最大的值。我们的策略是：
这道题要求在一个循环前缀中求出最小周期长度和最大频率。我们可以用 KMP 的 next 数组来解这个问题。我们先来回顾一下 next 数组的含义。\(next[i]\)代表在区间\(str[1,i]\)中前缀后缀的最长公共部分。如果区间长度是\(next[i]\)的倍数，那么其中就有循环节。详细见代码。