树上倍增

· · 个人记录

1.二进制问题

众所周知，任意正整数都可以被表示成若干个不同的2的非负整数幂的和。

\mathbf{For\,Example:} \color{Green}5=1+4=2^0+2^2 \color{Green}7=1+2+4=2^0+2^1+2^2

那么我们注意到，这些加数不会超过O(log x)个，所以这启示我们对于有结合率的信息，我们可以对每个元素维护以它为起点连续2^i个元素的信息。在查询的时候找出对应的O(log n)个信息加以合并就行啦。

2.一些典型具有结合律的信息

①元素和

②k级祖先

③矩阵乘积

④按位异或

……

3.树上k级祖先

给定一棵树，有q次询问，每次给定一个节点u，查询它的k级祖先。

规定：u的0级祖先是自己，1级祖先是父节点，2级祖先是父节点的父节点……即k级祖先是k-1级祖先的父节点。

问题：怎么用树上倍增维护k级祖先？

考虑刚才提到的二进制，对于u维护它的2^i级祖先的信息。

\because\color{Red}2^i=2^{i-1}+2^{i-1} 设$f_{i,u}$表示u的$2^i$级祖先，我们有： $\color{Blue}f_{i+1,u}=f_{i,f_{i,u}}

写成数组就是f[i+1][u]=f[i][f[i][u]]

预处理出所有结点的所有2^i级祖先的时间复杂度就是O(log n)

提醒：考虑到缓存命中问题，将i那一维开在外面可以显著提升程序效率。（f[i][u]）

4.查询k级祖先

我们把问题转化一下：给定一个数x，怎么把它分解成若干个不同的2的非负整数幂的和？

先给你一个引理：

对于任意的i，我们都有：

2^i>\sum\limits_{j=0}^{i-1}2^j=2^0+2^1+……+2^{i-1}

证明：

其实证明还蛮简单的，就是用二进制很容易想明白。2^i的二进制第i位为1，\sum_{j=0}^{i-1}2^i的第0->(i-1)位是1，第i位是0，显然2^i更大。

也就是说：对于一个x，如果能找到一个最大的i使得x\leq2^i，则我们分解的式子里肯定有2^i。（为什么？因为i是最大的，比i更大的幂次都不能选，所以如果没有2^i，即使把2^0,2^1,……,2^{i-1}都选了也要比2^i小，又不能重复，也就凑不出x）

有了这个结论，我们就得到了一个分解幂和贪心算法：

从大到小枚举幂次i，如果当前要被分解的数x满足x\leq2^i，就选上i，然后x-=2^i。

所以查询k级祖先时，我们只需要枚举幂次i，维护当前节点u，若k\leq2^i，则令u=f_{i,u}，k=k-2^i。

这个枚举的上界是树高的对数log h，最坏情况下等于log n。

于是一次查询的时间复杂度也是O(log n)。