哈夫曼树优化分治的思考题

· · 算法·理论

哈夫曼树其实用处挺大的！
第一题：有 n 个物品，每个物品有权值，有一个栈，初始时栈是空的。你可以执行以下两个操作之一：

  1. 任意将一个栈外的物品放进栈顶，消耗它的权值的代价。
  2. 将栈顶的物品取出，消耗它的权值的代价。

你需要使得每一个物品，都有一个时刻使得当前只有这个物品在栈外，其余物品在栈内，求代价为 v\log v 级别的操作方法。

做法：
给这些点建造 2 叉哈夫曼树，从根开始 DFS，递归到一个儿子时令当前儿子内部物品全部出栈，另一个儿子内全部物品进栈，递归另一个儿子时同理。可以发现这相当于一个分治的过程。

第二题：在树上每一个点上有物品，物品没有权值，有一个栈，初始时栈是空的。你可以执行以下两个操作之一：

  1. 任意将一个栈外的物品放进栈顶，消耗 1 的代价。
  2. 将栈顶的物品取出并放回原来位置，消耗 1 的代价。

你需要使得每一个物品，都有一个时刻使得当前只有这个物品及它的子树内的全部物品不在栈中，其余物品均在栈中，求代价为 n\log n 级别的操作方法。

做法：树链剖分，对于每一个重链顶点，执行这样的操作：
先使得重链上全部点满足一遍条件。
然后将这条链下面所连全部轻边连接的子树按照大小作为权值做类似第一题的方法建树并递归。
复杂度易知是 n\log n 级别的。