背景知识

二进制拆分

1. 快速幂运算 在快速幂运算中，可以表示成，二进制拆分使得幂运算的复杂度降为
2. 有限背包问题 有限背包问题中，假设A物品有13个，我们可以把它拆成四个物品，这四个物品可以凑出0->13的所有组合。

预处理思想

1. 前缀和与差分 前缀和可以快速求子区间和。O(1) 差分可以快速对数组子区间做加减法。O(1)

问题背景

快速求数组子区间最值。 我们考虑前缀和能不能做。 原数组：1 4 3 2 5 前缀最值数组：1 4 4 4 5 现在想要原数组中3 2的最值，无法通过前缀最值数组得到。 因为最值不具有可减性。

ST表

以求区间最大值举例。数组为h。 我们定义数组rmax[i][j]表示从第个数开始，长度为的区间最大值。

rmax[i][0] = h[i]   // 长度为1的区间最值就是自己
// 大区间最值由两个小区间组成
rmax[i][expo] = max(rmax[i][expo - 1], rmax[i + (1 << expo - 1) - 1][expo - 1]);
// 举个例子，从第2个数开始，长度为4的区间，可以由两个长度为2的区间拼接得到。
rmax[2][2] = max(rmax[2][1], rmax[4][1]);

// ST表初始化函数
void init() {  // O(nlogn)
    for (int i = 1; i <= n; i++) { // 长度为1的区间
        rmax[i][0] = h[i];
        rmin[i][0] = h[i];
    } // expo: exponent指数  O(nlogn)
    for (int expo = 1; expo <= 16; expo++) {  // 区间长度的幂指数
        for (int i = 1; i + (1 << expo) - 1 <= n; i++) { // 左端点
            rmax[i][expo] = max(rmax[i][expo - 1], rmax[i + (1 << expo - 1)][expo - 1]);
            rmin[i][expo] = min(rmin[i][expo - 1], rmin[i + (1 << expo - 1)][expo - 1]);
        }
    }
}

ST表的初始化，可以类比区间DP，区间长度是递推的阶段，在ST表中长度用幂指数表示罢了。通过小区间的值计算大区间的值。

那么有了ST表之后，怎么计算任意区间最值呢，我们可以对区间长度做二进制拆分。 例如，长度为7的区间可以拆分成1 + 2 + 4，合并这三段区间的最值。 这样二进制拆分对应的查询复杂度是O(logn)。

// 查询区间[a, b]最大值的函数
int query_max(int a, int b) {
    int len = b - a + 1;  // 计算区间长度
    int cur = 0;          // 初始值是2^0
    int maxx = INT_MIN;   // 擂台上放个最小值
    while (len) {         // 对len做二进制拆分
        if (len & 1) {    // 当前位存在
            maxx = max(maxx, rmax[a][cur]);  // 记录子区间结果
            a += (1 << cur);                 // 移动区间左端点到下一个区间开始处
        }
        cur++;
        len >>= 1;
    }
    
    return maxx;
}

有没有方法进一步降低查询的时间复杂度呢？ 举例：数组1 4 2 5 3 想要求整个数组(长度为5)的最大值。ST表中存的是所有2的幂次的区间最值。 距离5最近的2的幂次是4。所以我们可以划两个长度为4的区间，一个从左端点出发，另一个从右端点出发，[1, 4], [2, 5]。这两个区间能够覆盖查询的范围。对这两个区间的最大值再求一次最大值即可。

在这里，重要的是求最大值中，一个数多次计算不影响结果（幂等性）。求gcd、lcm也符合这样的特点。

来看代码：

int log_2[50005];
for (int i = 2;i <= n; i++) { // 对数计算可以用递推实现，预处理出一张表格
    log_2[i] = log_2[i >> 1] + 1;
}

int query_max(int a, int b) { // O(logn)
    int len = b - a + 1;      // 计算待求区间长度
    int expo = log_2[len];    // 最接近len的2的幂次，其实就是对len取对数，下取整
    int maxx = max(rmax[a][expo], rmax[b - (1 << expo) + 1][expo]); // 这里需要计算右侧小区间的左端点b - (1 << expo) + 1
    return maxx;
}

例题

ST表模板_洛谷 (opens new window)

#include <bits/stdc++.h>
using namespace std;

const int N = 50005;
int rmax[N][16];
int rmin[N][16];
int n, q;
int h[N];
int log_2[N]; // 存幂指数

void init() {  // O(nlogn)
    for (int i = 1; i <= n; i++) { // 长度为1的区间
        rmax[i][0] = h[i];
        rmin[i][0] = h[i];
    } // expo: exponent指数  O(nlogn)
    for (int expo = 1; expo <= 16; expo++) {  // 区间长度的幂指数
        for (int i = 1; i + (1 << expo) - 1 <= n; i++) { // 左端点
            rmax[i][expo] = max(rmax[i][expo - 1], rmax[i + (1 << expo - 1)][expo - 1]);
            rmin[i][expo] = min(rmin[i][expo - 1], rmin[i + (1 << expo - 1)][expo - 1]);
        }
    }
}

int query_max_min(int a, int b) { // O(logn)
    int len = b - a + 1;    // 计算待求区间长度
    int expo = log_2[len];  // 最接近len的2的幂次
    int maxx = max(rmax[a][expo], rmax[b - (1 << expo) + 1][expo]);
    int minn = min(rmin[a][expo], rmin[b - (1 << expo) + 1][expo]);
    
    return maxx - minn;
}

int main(void) {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
    }

    init();

    for (int i = 2; i <= n; i++) {    // 对数的预处理
        log_2[i] = log_2[i >> 1] + 1;
    }

    while (q--) { // q轮查询
        int a, b;
        cin >> a >> b;
        cout << query_max_min(a, b) << endl;
    }
    return 0;
}

树上倍增

我们讨论下最近公共祖先一题。 LCA模板_洛谷 (opens new window)

基本解法

dfs遍历记录各结点深度，根节点为1。同时记录各结点的父结点。 假设待求LCA两结点为a，b。 算一算他们俩的深度，若深度不一致，则将较深节点向上提u = fa[u]。深度一致时，两结点同步向上提，直到相同为止。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
vector<int> G[N];
int fa[N], d[N];

void dfs(int u) {
    for (auto v : G[u]) {
        if (v == fa[u]) continue; // 排除父节点
        fa[v] = u;
        d[v] = d[u] + 1;
        dfs(v);
    }
}

int QueryLCA(int u, int v) {
    if (d[u] < d[v]) swap(u, v); // u存放更深的节点
    while (d[u] != d[v]) u = fa[u];
    while (u != v) {
        u = fa[u];
        v = fa[v];
    }
    return u;
}

int main(void) {
    int n, m, rt;
    cin >> n >> m >> rt;

    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    d[rt] = 1;
    dfs(rt);
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        cout << QueryLCA(u, v) << endl;
    }
    return 0;
}

倍增算法

在上述方法中涉及到两次结点提升。

1. 深度不一致，提升深度较大结点。
2. 深度一致，共同提升，直到相等。

如果我们可以直到某个结点的1, 2, 4, 8, ...级祖先，是不是可以加速提升过程呢？

我们用anc[i][j]表示i号结点的第级祖先 anc[i][0]就是父节点。 同样可以通过1级父节点计算2级父节点，对该数组做一个初始化。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;
vector<int> G[N];
int d[N];
int anc[N][20];  // i点向上提2^j层对应的点  ancestor
int n, m, rt;


void dfs(int u) {
    for (auto v : G[u]) {
        if (v == anc[u][0]) continue; // 排除父节点
        anc[v][0] = u;
        d[v] = d[u] + 1;
        dfs(v);
    }
}

void init() {
    for (int j = 1; j <= 18; j++) { // 枚举长度(幂指数)
        for (int i = 1; i <= n; i++) {
            anc[i][j] = anc[anc[i][j - 1]][j - 1];
        }
    }
}

int QueryLCA(int u, int v) {
    if (d[u] < d[v]) swap(u, v); // u存放更深的节点
    for (int i = 18; i >= 0; i--) {
        if (d[anc[u][i]] >= d[v]) {
            u = anc[u][i];
        }
    }
    if (u == v) return u;
    for (int i = 18; i >= 0; i--) {
        if (anc[u][i] != anc[v][i]) { // 相等可能已经不是最近的了，所以不相等才向上提升。
            u = anc[u][i];
            v = anc[v][i];
        }
    }
    return anc[u][0]; // 由于上方不等号的逻辑，最终结果，u的父亲就是公共祖先。
}

int main(void) {
    cin >> n >> m >> rt;

    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }

    d[rt] = 1;   // 关键，否则第31行恒成立。
    dfs(rt);
    init();
    
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        cout << QueryLCA(u, v) << endl;
    }
    return 0;
}