倍增

和双指针一样，倍增也是一种解决问题的思想，不局限与某种特定题型，只要是能用到长序列的情况，都有可能用到倍增算法，需要我们能够敏锐得发现题目中的特性，利用倍增思路解决问题。

倍增法（英语：binary lifting），顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理，大大地优化时间复杂度。

RMQ问题

RMQ问题，即Range Minimum/Maximum Query（区间最大/最小值）问题

例题讲解

P3865 【模板】ST 表 && RMQ 问题 - 洛谷

给定一个长度为 $N$ 的数列，和 $ M $ 次询问，求出每一次询问的区间内数字的最大值。

暴力解法

对于每个给定的$l$和$r$，我们用一个for循环枚举所有的元素，然后对其取$max$即可

但是由于数组的长度为$N$，且询问的次数为$M$，可以计算，时间复杂度是$O(NM)$的，这是不能接受的

为此，我们可以利用最值问题的一个“可重复贡献”的特点，利用倍增思路进行求解

然后我们就要用到利用倍增思路产生的一个辅助表：ST表

ST表

ST 表（Sparse Table，稀疏表）是用于解决 可重复贡献问题 的数据结构。

可以很容易发现，对于{0, 13, 14, 4, 13, 1, 5, 7}这样的一个数组来说，对{0, 13, 14, 4, 13}部分取最大值记为$x$，对{4, 13, 1, 5, 7}这部分取最大值记为$y$，再对$x$和$y$取最大值，就是整个数组的最大值，由于两段区间有重叠部分{4, 13}，这两个数在计算贡献的时候被算了两次，但是重复的计算并不会对整体的答案产生影响，对于这样的一种性质，我们把它叫做可重复贡献

具体实现方式，这里贴了OI-WIKI的介绍

ST 表基于 倍增 思想，可以做到 $\Theta(n\log n)$ 预处理，$\Theta(1)$ 回答每个询问。但是不支持修改操作。

基于倍增思想，我们考虑如何求出区间最大值。可以发现，如果按照一般的倍增流程，每次跳 $2^i$ 步的话，询问时的复杂度仍旧是 $\Theta(\log n)$，并没有比线段树更优，反而预处理一步还比线段树慢。

我们发现 $\max(x,x)=x$，也就是说，区间最大值是一个具有「可重复贡献」性质的问题。即使用来求解的预处理区间有重叠部分，只要这些区间的并是所求的区间，最终计算出的答案就是正确的。

如果手动模拟一下，可以发现我们能使用至多两个预处理过的区间来覆盖询问区间，也就是说询问时的时间复杂度可以被降至 $\Theta(1)$，在处理有大量询问的题目时十分有效。

具体实现如下：

令 $f(i,j)$ 表示区间 $[i,i+2^j-1]$ 的最大值。

显然 $f(i,0)=a_i$。

根据定义式，第二维就相当于倍增的时候「跳了 $2^j-1$ 步」，依据倍增的思路，写出状态转移方程：$f(i,j)=\max(f(i,j-1),f(i+2^{j-1},j-1))$。

以上就是预处理部分。而对于查询，可以简单实现如下：

对于每个询问 $[l,r]$，我们把它分成两部分：$[l,l+2^s-1]$ 与 $[r-2^s+1,r]$，其中 $s=\left\lfloor\log_2(r-l+1)\right\rfloor$。两部分的结果的最大值就是回答。

根据上面对于「可重复贡献问题」的论证，由于最大值是「可重复贡献问题」，重叠并不会对区间最大值产生影响。又因为这两个区间完全覆盖了 $[l,r]$，可以保证答案的正确性。

代码实现

const int N = 1e5 + 10, M = 2e6 + 10;

int n, m;
int a[N];
int st[N][20];
int log2n[N];

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];

    for (int i = 1; i <= n; i ++ ) st[i][0] = a[i];
    for (int i = 1; i < 17; i ++ ) {
        for (int j = 1; j + (1 << (i - 1)) <= n; j ++ ) {
            st[j][i] = std::max(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
        }
    }

    int p = 0, c = 2;
    for (int i = 1; i <= n; i ++ ) {
        if (i == c) {
            c *= 2;
            p ++;
        }
        log2n[i] = p;
    }

    while (m --) {
        int l, r;
        cin >> l >> r;
        int x = log2n[(r - l + 1)];
        int ans = std::max(st[l][x], st[r - (1 << x) + 1][x]);
        cout << ans << "\n";
    }
}

LCA问题

最近公共祖先简称 LCA（Lowest Common Ancestor）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。
为了方便，我们记某点集 $S={v_1,v_2,\ldots,v_n}$ 的最近公共祖先为 $\text{LCA}(v_1,v_2,\ldots,v_n)$ 或 $\text{LCA}(S)$。

性质

本节 性质 部分内容翻译自 wcipeg，并做过修改。

1. $\text{LCA}({u})=u$；
2. $u$ 是 $v$ 的祖先，当且仅当 $\text{LCA}(u,v)=u$；
3. 如果 $u$ 不为 $v$ 的祖先并且 $v$ 不为 $u$ 的祖先，那么 $u,v$ 分别处于 $\text{LCA}(u,v)$ 的两棵不同子树中；
4. 前序遍历中，$\text{LCA}(S)$ 出现在所有 $S$ 中元素之前，后序遍历中 $\text{LCA}(S)$ 则出现在所有 $S$ 中元素之后；
5. 两点集并的最近公共祖先为两点集分别的最近公共祖先的最近公共祖先，即 $\text{LCA}(A\cup B)=\text{LCA}(\text{LCA}(A), \text{LCA}(B))$；
6. 两点的最近公共祖先必定处在树上两点间的最短路上；
7. $d(u,v)=h(u)+h(v)-2h(\text{LCA}(u,v))$，其中 $d$ 是树上两点间的距离，$h$ 代表某点到树根的距离。

求法

朴素算法

过程

可以每次找深度比较大的那个点，让它向上跳。显然在树上，这两个点最后一定会相遇，相遇的位置就是想要求的 LCA。
或者先向上调整深度较大的点，令他们深度相同，然后再共同向上跳转，最后也一定会相遇。

性质

朴素算法预处理时需要 dfs 整棵树，时间复杂度为 $O(n)$，单次查询时间复杂度为 $\Theta(n)$。如果树满足随机性质，则时间复杂度与这种随机树的期望高度有关。

倍增算法

过程

倍增算法是最经典的 LCA 求法，他是朴素算法的改进算法。通过预处理 $\text{fa}{x,i}$ 数组，游标可以快速移动，大幅减少了游标跳转次数。$\text{fa}{x,i}$ 表示点 $x$ 的第 $2^i$ 个祖先。$\text{fa}_{x,i}$ 数组可以通过 dfs 预处理出来。

现在我们看看如何优化这些跳转：
在调整游标的第一阶段中，我们要将 $u,v$ 两点跳转到同一深度。我们可以计算出 $u,v$ 两点的深度之差，设其为 $y$。通过将 $y$ 进行二进制拆分，我们将 $y$ 次游标跳转优化为「$y$ 的二进制表示所含 1 的个数」次游标跳转。
在第二阶段中，我们从最大的 $i$ 开始循环尝试，一直尝试到 $0$（包括 $0$），如果 $\text{fa}{u,i}\not=\text{fa}{v,i}$，则 $u\gets\text{fa}{u,i},v\gets\text{fa}{v,i}$，那么最后的 LCA 为 $\text{fa}_{u,0}$。

性质

倍增算法的预处理时间复杂度为 $O(n \log n)$，单次查询时间复杂度为 $O(\log n)$。
另外倍增算法可以通过交换 fa 数组的两维使较小维放在前面。这样可以减少 cache miss 次数，提高程序效率。

模板题

P3379 【模板】最近公共祖先（LCA） - 洛谷 | 计算机科学教育新生态

const int N = 5e5 + 10;

int n, m, root;
std::vector<int> g[N];
int act[20][N];
int dep[N];

void init_act(int u, int pa) {
    act[0][u] = pa;
    if (pa == -1) dep[u] = 1;
    else dep[u] = dep[pa] + 1;
    for (int i = 1; i < 20; i ++ ) act[i][u] = act[i - 1][act[i - 1][u]];

    for (auto v: g[u]) {
        if (v == pa) continue;
        init_act(v, u);
    }
}

int get_lca(int x, int y) {
    if (x == y) return x;

    if (dep[x] < dep[y]) std::swap(x, y);
    int k = dep[x] - dep[y];
    for (int i = 0; i < 19; i ++ ) {
        if (k >> i & 1) x = act[i][x];
    }
    if (x == y) return x;

    for (int i = 19; i >= 0; i -- ) {
        if (act[i][x] != act[i][y]) x = act[i][x], y = act[i][y];
    }
    return act[0][x];
}

void solve() {
    cin >> n >> m >> root;
    for (int i = 1; i < n; i ++ ) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    init_act(root, -1);

    while (m --) {
        int a, b;
        cin >> a >> b;
        int lca = get_lca(a, b);
        cout << lca << "\n";
    }

}