倍增

概念讲解

什么是倍增？

倍增是利用二进制拆分思想，快速跳转到目标位置的技巧。

核心思想

将步数用二进制表示，每次跳 $2^k$ 步。

ST 表（RMQ）

问题

静态区间最值查询。

实现

123456789101112131415161718const int N = 100005;
const int LOG = 20;
int st[N][LOG];
int a[N];

void build(int n) {
    for (int i = 1; i <= n; i++) st[i][0] = a[i];
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            st[i][j] = max(st[i][j-1], st[i + (1 << (j-1))][j-1]);
        }
    }
}

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

时间复杂度：建 $O(n \log n)$，查 $O(1)$

LCA（倍增法）

问题

求树上两点的最近公共祖先。

实现

12345678910111213141516171819202122232425262728const int LOG = 20;
int parent[N][LOG];
int depth[N];

void buildLCA(int n) {
    for (int j = 1; j < LOG; j++) {
        for (int i = 1; i <= n; i++) {
            parent[i][j] = parent[parent[i][j-1]][j-1];
        }
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    for (int j = LOG - 1; j >= 0; j--) {
        if (depth[u] - (1 << j) >= depth[v]) {
            u = parent[u][j];
        }
    }
    if (u == v) return u;
    for (int j = LOG - 1; j >= 0; j--) {
        if (parent[u][j] != parent[v][j]) {
            u = parent[u][j];
            v = parent[v][j];
        }
    }
    return parent[u][0];
}

考点分析

初赛考查方式

1. 程序阅读： 倍增程序
2. 编程题： LCA、ST 表

常见考点

• ST 表
• LCA 倍增法
• 倍增思想

例题精讲

例题 1：LCA

题目： 求树上两点的 LCA。

解答：

先将深度大的点上移到同一深度，再一起上移。

练习题

1. 倍增的核心思想是什么？

2. ST 表的查询时间复杂度是多少？

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

3. LCA 倍增法的时间复杂度是多少？

易错点

⚠️ 注意：

1. LOG 要足够大（通常 20）
2. 要先处理深度差
3. 从大到小枚举
4. 注意边界条件