倍增

倍增思想是一种通过逐步增加步长来进行有效计算的一种策略。在计算机科学和算法设计中，倍增思想常常用于提高算法的效率，特别是在处理一些需要多次迭代或逐层递进的问题时。在倍增思想中，问题的规模以指数级别增加，但每次迭代的计算量相对较小。这使得算法的整体复杂度得到有效的控制。

通俗点来说，倍增的思想一般就是按照 2 的倍数不断增大，比如 1，2，4，8，16，32，64 …… 指数级别的增长是非常快，而且数值是非常爆炸的。

比如二分查找一个数的时候，对于 [1，2000000] 这个区间我们查找一个 $x=1000000$ （1e6），2 的 20 次方就已经超过了 $x$ ，本来我们要遍历 1e6 次才能查到，但二分查找的话不到 20 次就能查到，让运行效率有了质的飞跃。

一些常见的应用和例子：二分查找、快速幂、ST 表、LCA 等。

// 一些可能会用到的数据范围： $2^{17}=131072$ 大于 1e5； $2^{18}=262144$ 大于 2e5； $2^{20}=1048576$ 稍微大于 1e6。

ST表

ST（Sparse Table）算法可以在 O(nlogn) 时间内进行预处理，然后在 O(1) 时间内回答每个查询。ST 表的基础运用一般是查询任意一个区间内的最值。ST 表效率高而且代码非常简短。但是 ST 表一般是静态查找，使用过程中不要有修改操作，如果涉及到区间修改还是考虑用线段树吧。

预处理

假设 $a[]$ 数组是初始序列， $f[i][j]$ 表示从第 $i$ 个数起连续 $2^j$ 个数中的最大值。

假设初始序列 2 3 5 7 4 1 3 9，则 $f[1][1]=max(2,3)= 3$ ； $f[2][2]=max(3,5,7,4)=7$ 。那么 $f[1][0]$ ，就是从第一个数起连续 $2^0$ （也就是1）长度的最大值，就是它自己。所以对于所有的 $f[i][0]$ 都是等于 $a[i]$ 的。

我们可以将除了 $j=0$ 的 $f[i][j]$ 都平均分成两段（因为除了 $j=0$ 外 $2^j$ 一定是偶数），从 $i$ 到 $i+2^{j-1}-1$ 为一段， $i+2^{j-1}$ 到 $i+2^j-1$ 为一段（长度都为 $2^{j-1}$ ）。

例如： $f[2][2]=max(max(3,5),max(7,4))$ 。（分成两半）

于是我们得到了状态转移方程 $f[i,j]=max(f[i,j-1],f[i+2^{j-1},j-1])$ 。

代码如下：

void ST(int n)
{
    // 初始化
    for (int i = 1; i <= n; i++)
        f[i][0] = a[i];
    // 从第i个数起连续2^j个数中的最大值
    for (int j = 1; (1 << j) <= n; j++) 
        for (int i = 1; i + (1 << j) - 1 <= n; i++) // 注意边界，1 << j 就是2的j次幂
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}

查询

假如我们需要查询的区间为（i，j），那么我们需要找到覆盖这个闭区间（左边界取 $i$ ，右边界取 $j$ ）的最小幂（可以重复，比如查询1，2，3，4，5，我们可以查询 max（1，2，3，4）和max（2，3，4，5），然后再取这两个值的max）。

因为这个区间的长度为 $j - i + 1$ ，所以我们可以取 $k=log2( j - i + 1)$ 。

则有： $MAX(i,j)=max(f[i][k],f[j-2^k+1][k])$ 。

例如，要求区间 [1，5] 的最大值， $k=log2(5-1+1)=2$ ，即求 $max(f[1][2],f[5-2^2+1][2])=max(f[1][2],f[2][2])$ 。

代码如下：

int RMQ(int l, int r)
{
    int s = Log2[r - l + 1]; // log2(r - l + 1)下取整
    return max(f[l][s], f[r - (1 << s) + 1][s]);
}

log2 也可以自己预处理先求出来，然后直接调用

1	for(int i = 2; i <= n; i ++) lg[i] = lg[i >> 1] + 1;

LCA

多叉树：与二叉树不同，多叉树允许一个节点拥有多个子节点。在多叉树中，每个节点可以有任意数量的子节点（可以有零个、一个、两个、三个……），而不仅仅是两个，就像一个没有回路的图。

LCA（Least Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点 u 和 v 最近的公共祖先。 ———来自百度百科

例如下图：

对于节点 3 和 4 的最近公共祖先就是节点 2；对于节点 3 和节点 5 的最近公共祖先就是节点 1。节点 3 和节点 2 的最近公共祖先是节点 2。

那么我们求两个节点的的 LCA 就会有一种非常显而易见的暴力做法，就是两个节点都一个点一个点的向上爬，直到出现第一个这两个点都走过的点，这个点就是它们的 LCA。

比如：节点 3 和节点 4

3 -> 2 -> 1

4 -> 2 -> 1

节点 2 是它们第一次相遇的点，那么节点 2 就是它们的 LCA。当然，在写代码的时候肯定不会走到节点 1，这样无疑是过多运行了。

但是对于这样的暴力找法，如果设这个树的深度是 n，那我们每一次的查找的时候最坏情况下的时间复杂度都是 O(logn)，做题时肯定不会就让查找几次，通常都是 1e5 级别的查找次数，一定 TLE 掉的。因此我们就要对做法进行优化，也就有了用倍增的方法来优化查找 LCA。（tarjan 等优化方法就不介绍了，学完图论后可以自己再去了解）。

至于倍增前面已经说过，这里就不过多描述了。对于 LCA 我们要注意的一点就是，我们在倍增跳跃时，不能从小到大跳，而是从大到小跳跃。因为从小到大跳跃经常会出现需要回溯的情况。

比如：对于 10，我们跳 1，2，4 之后 $7 != 10$ ，接着跳 8 就变成了 $15 > 10$ ，就要回溯，直到找到 $2 + 8 = 10$ 这种情况。但是如果我们从大到小跳，就不会出现这种情况，不大于 10 的最大 2 整次幂就是 8， $10 - 8 = 2$ ，不大于 2 的整次幂就是 2。我们就很容易的得到 $10 = 8 + 2$ 。极大的降低了算法复杂度。

有了倍增后，对于深度为 n 的树，我们每次查找都只需要 O(logn) 的时间复杂度，可以满足绝大多数题目的要求，除非题目并不打算考察 LCA。

对于倍增求 LCA，我们也要先预处理每个节点在向上跳 $2^i$ 步之后会跳到哪个节点。也需要记录每个节点的深度。假设 $dep[i]$ 是节点 $i$ 的深度， $f[i][j]$ 是节点 $i$ 在向上跳 $2^j$ 步后的节点。

因为还没有讲图论，所以这里简单介绍一下用 vector 建图（邻接表）。

vector建图

比如：点x和y之间有一条无向边

1 2	v[x].push_back(y); v[y].push_back(x);

比如：节点 1 和 2 有一条无向边并且节点 1 和 4、节点2 和 3、节点 2 和 5、节点 2 和 6 都连着一条无向边。那么：

v[1].push_back(2), v[2].push_back(1);
v[1].push_back(4), v[4].push_back(1);
v[2].push_back(3), v[3].push_back(2);
v[2].push_back(5), v[5].push_back(2);
v[2].push_back(6), v[6].push_back(2);
// vecotr 内的元素下标从 0 开始
// v[1][0] = 2, v[1][1] = 4    // v[1] 里面就有 2，4两个元素，遍历里面的元素就是它们连着的点
// v[2][0] = 3, v[2][1] = 5, v[2][2] = 6
// 其他点也如此

求节点深度

常用的一般有两种求法，dfs 和 bfs，在这里我就放一下 bfs 的板子。

需要注意的是根节点的深度是1，具体还是看注释。

void bfs(int root)
{
    memset(dep, 0x3f, sizeof dep);
    dep[0] = 0, dep[root] = 1;
    q.push(root);
    while(q.size())
    {
        int t = q.front();
        q.pop();
        for(int i = 0; i < v[t].size(); i ++)
        {
            int z = v[t][i];
            if(dep[z] > dep[t] + 1)
            {
                // z 的父节点是 t，那么节点z的深度就等于节点t的深度加一。
                dep[z] = dep[t] + 1;
                q.push(z);
                // z 的父节点是 t，那么节点z向上跳1步就是t节点。
                f[z][0] = t;
                // 下面这段for循环是预处理 f[i][j]，也是算法的核心之一
//意思就是节点z向上跳 2^j 步所到达的节点，就是从 z 向上跳 2^(j-1) 步后到达的节点再向跳 2^(j-1)步
                // 因为 2^j = 2^(j-1) + 2^(j-1)
                for(int j = 1; j <= 20; j ++)
                    f[z][j] = f[f[z][j-1]][j-1];
            }
        }
    }
}

LCA 查询

查询两个结点 u 和 v 的 LCA 时，我们先让节点 u 和节点 v 都跳到同一深度，判断其中一个节点是否是另外一个节点的祖宗节点，如果是的话就返回。如果不是的话，我们再让两个结点一起向上跳，最后跳到它们最近公共祖先下方的节点位置（注意是跳到最近公共祖先下面的节点），然后再返回当前节点的父节点就行了（因为跳到的是 LCA 的下面，所以父节点就是 LCA）。

代码如下：

int query(int a, int b)
{
    // 如果节点a的深度小于节点 b，那么说明节点a在节点b的上方，方便操作交换即可
    if(dep[a] < dep[b]) swap(a, b);

    // 将节点a一直向上跳，直到跳到节点b同一深度
    // 不用担心越界问题，因为f[a][i]如果越过树的深度，那么它的值是零
    // 又因为 dep[b]的值一定大于1，所以if语句不会成立
    for(int i = 20; i >= 0; i --)
        if(dep[f[a][i]] >= dep[b])
            a = f[a][i];
    if(a == b) return a; // 如果其中一个节点是另外一个节点的祖宗节点，返回即可

    // a 和 b 都向上跳跃，直到 a 向上跳一步和 b 向上跳一步之后，它们的父节点是同一个节点为止
    // 此时它们就位于 LCA 下方的节点
    // 同样不用担心越界问题，如果越过树的深度，f[a][i]和f[b][i]都是0，两值相等，if语句不运行
    for(int i = 20; i >= 0; i --)
        if(f[a][i] != f[b][i])
        {
            a = f[a][i];
            b = f[b][i];
        }
    return f[a][0]; // 返回它的父节点
}

后记：

在预处理完毕后去找 LCA 时，为了让它跑得快一些，我们可以通过预处理 log 来进行一个常数优化

// 预处理出 log2[i] + 1 的值
for(int i = 1; i <= n; ++i) lg[i] = lg[i-1] + (1 << lg[i-1] == i);

// 等同于先将 log2[1] = 1，赋值后，递推求log2值 
// log2[1] 的实际值是 = 0，此处只是用来递推log2[i] + 1
// 等同于下面一段代码
lg[1] = 1;
for(int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1; 

// 注意不要与ST表中的log2预处理弄混，ST表中预处理的是log2[i]，这里预处理的是log2[i]+1