53 · 倍增与 ST 表

倍增只有一个动作：先把“走 2^k 步之后到哪”全部算出来，再把任意步数拆成二进制去拼。正整数的二进制分解唯一，所以 10⁵ 步最多拆成 17 段，每段长度都是 2 的幂。这一节用它做两件事：O(1) 的静态区间最值（ST 表）、O(log n) 的树上 LCA。

先把两个工具拆开。第一个是 lg 数组——它只有四行代码，但决定了查询能不能真的 O(1)；第二个是 ST 表本身的定义与递推。

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

int lg2v[10];

int main() {
    lg2v[1] = 0;                                  // 2^0 = 1
    for (int i = 2; i <= 8; ++i) lg2v[i] = lg2v[i >> 1] + 1;

    for (int i = 1; i <= 8; ++i) cout << i << " -> " << lg2v[i] << "\n";
    // 1 -> 0    2 -> 1    3 -> 1    4 -> 2
    // 5 -> 2    6 -> 2    7 -> 2    8 -> 3
    return 0;
}

// n = 1e5，K = 17（2^16 = 65536 <= 1e5 < 2^17）
int st[17][100005], lg2v[100005];

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

for (int k = 1; (1 << k) <= n; ++k)                       // 只要 2^k <= n 就有合法区间
    for (int i = 1; i + (1 << k) - 1 <= n; ++i)           // 右端点不能越过 n
        st[k][i] = max(st[k-1][i], st[k-1][i + (1 << (k-1))]);

int query(int l, int r) {
    int k = lg2v[r - l + 1];
    return max(st[k][l], st[k][r - (1 << k) + 1]);
}

这两块拼起来就是 ST 表模板。下面这道题把 m 堆到 2×10⁶，正是逼你把单次查询压到 O(1) 的经典设置——线段树 O(log n) 会多出一个 17 的常数，在 3.4×10⁷ 次操作上就是过与不过的差别。

lg2v[1] = 0
for i = 2 .. n:  lg2v[i] = lg2v[i >> 1] + 1        // ① 长度 -> 层号

st[0][i] = a[i]                                     // ② 第 0 层就是原数组
for k = 1 .. while 2^k <= n:
    for i = 1 .. n - 2^k + 1:
        st[k][i] = max(st[k-1][i], st[k-1][i + 2^(k-1)])

query(l, r):
    k = lg2v[r - l + 1]                             // ③ 两段拼接
    return max(st[k][l], st[k][r - 2^k + 1])

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

const int N = 100005;
const int K = 17;                       // 2^16 = 65536 <= 1e5 < 2^17，层数最多到 16

int st[K][N];                           // st[k][i]：区间 [i, i + 2^k - 1] 的最大值
int lg2v[N];                            // lg2v[len] = floor(log2(len))

int main() {
    int n, m;
    scanf("%d %d", &n, &m);             // m 到 2e6，用 scanf/printf 比 cin/cout 稳

    for (int i = 1; i <= n; ++i) scanf("%d", &st[0][i]);   // 第 0 层直接读入，省掉 a[]

    lg2v[1] = 0;                                            // 长度 1 只需要第 0 层
    for (int i = 2; i <= n; ++i) lg2v[i] = lg2v[i >> 1] + 1;

    // 递推：长度 2^k 的区间 = 左右两个长度 2^(k-1) 的区间
    for (int k = 1; (1 << k) <= n; ++k)
        for (int i = 1; i + (1 << k) - 1 <= n; ++i)         // 右端点不越界
            st[k][i] = max(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]);

    while (m--) {
        int l, r;
        scanf("%d %d", &l, &r);
        int k = lg2v[r - l + 1];                            // 2^k <= 长度 < 2^(k+1)
        // 左段以 l 开头，右段以 r 结尾；两段必然覆盖整个区间
        printf("%d\n", max(st[k][l], st[k][r - (1 << k) + 1]));
    }
    return 0;
}

ST 表是倍增在“数组上的一段”里的用法。同一个思想在树上是求 LCA：给定以 s 为根的树和两点 u、v，求它们最近的公共祖先。

朴素做法：从 u 一路往上走，把经过的点打上标记；再从 v 往上走，第一次踩到标记的点就是 LCA。单次 O(深度)，5×10⁵ 次询问在一条链上直接退化成 2.5×10¹¹ 次操作。倍增把它压到 O(log n)：只预存“往上跳 2^k 步到哪”这 n log n 个位置。

// 建表（跟 BFS 一起做，避免链状树爆栈）
void bfs(int root) {
    queue<int> q; q.push(root); dep[root] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int k = 1; k < K; ++k) up[k][u] = up[k-1][up[k-1][u]];
        for (int e = head[u]; e; e = nxt[e]) {
            int v = to[e];
            if (v == up[0][u]) continue;      // 跳过父亲
            up[0][v] = u; dep[v] = dep[u] + 1;
            q.push(v);
        }
    }
}

// up[k][3] 的含义：从 3 号点往上跳 2^k 步
// 例：路径 3 -> 5 -> 8 -> 12 -> 1 -> 0（0 是树外的哨兵）
//     up[0][3] = 5    往上第 1 步
//     up[1][3] = 8    往上第 2 步（= up[0][up[0][3]]）
//     up[2][3] = 1    往上第 4 步（= up[1][up[1][3]] = up[1][8]）

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

const int N = 500005;                  // P3379 的量级：5×10^5 个点
const int K = 20;                      // 2^18 = 262144 <= 5e5 < 2^19，层数到 18，开 20 留余量

int head[N], nxt[N << 1], to[N << 1], ecnt;   // 链式前向星（第 41 节）
int up[K][N], dep[N];

void addEdge(int u, int v) {
    to[++ecnt] = v; nxt[ecnt] = head[u]; head[u] = ecnt;
}

void bfs(int root) {
    queue<int> q;
    q.push(root);
    dep[root] = 1;                     // 根的深度设 1，于是 dep[0] = 0 天然是哨兵
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int k = 1; k < K; ++k)    // 整行一次算完：2^k = 2^(k-1) + 2^(k-1)
            up[k][u] = up[k - 1][up[k - 1][u]];
        for (int e = head[u]; e; e = nxt[e]) {
            int v = to[e];
            if (v == up[0][u]) continue;         // 无向边存了两遍，跳过父亲
            up[0][v] = u;                        // 儿子的一级祖先就是 u
            dep[v] = dep[u] + 1;
            q.push(v);
        }
    }
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);   // 让 u 更深
    int d = dep[u] - dep[v];
    for (int k = 0; k < K; ++k)        // 深度差按二进制拆开，逐位往上跳
        if (d >> k & 1) u = up[k][u];
    if (u == v) return u;              // v 本来就是 u 的祖先
    for (int k = K - 1; k >= 0; --k)   // 从大到小试：跳完还不同就跳
        if (up[k][u] != up[k][v]) { u = up[k][u]; v = up[k][v]; }
    return up[0][u];                   // 此时 u、v 是 LCA 的两个儿子
}

int main() {
    int n, m, s;
    scanf("%d %d %d", &n, &m, &s);
    for (int i = 1; i < n; ++i) {
        int u, v; scanf("%d %d", &u, &v);
        addEdge(u, v); addEdge(v, u);
    }
    bfs(s);
    while (m--) {
        int a, b; scanf("%d %d", &a, &b);
        printf("%d\n", lca(a, b));
    }
    return 0;
}

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

const int N = 50005;
const int K = 17;                       // 2^15 = 32768 <= 5e4 < 65536，层数最多到 15

int mx[K][N], mn[K][N];
int lg2v[N];

int main() {
    int n, q;
    scanf("%d %d", &n, &q);

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

    for (int i = 1; i <= n; ++i) {
        int x; scanf("%d", &x);
        mx[0][i] = mn[0][i] = x;        // 长度 1 的区间，最大最小都是自己
    }

    for (int k = 1; (1 << k) <= n; ++k) {
        for (int i = 1; i + (1 << k) - 1 <= n; ++i) {
            int j = i + (1 << (k - 1));             // 右半段的左端点
            mx[k][i] = max(mx[k - 1][i], mx[k - 1][j]);
            mn[k][i] = min(mn[k - 1][i], mn[k - 1][j]);
        }
    }

    while (q--) {
        int a, b;
        scanf("%d %d", &a, &b);
        int k = lg2v[b - a + 1];
        int hi = max(mx[k][a], mx[k][b - (1 << k) + 1]);
        int lo = min(mn[k][a], mn[k][b - (1 << k) + 1]);
        printf("%d\n", hi - lo);         // 身高差，不是和
    }
    return 0;
}