Sparse Table 与倍增

前言

线段树可以在 $O(\log n)$ 时间内做区间查询。但如果数组永远不变呢？能不能预处理一次，然后每次查询只要 $O(1)$？

Sparse Table 就是为此而生的。它预处理 $O(n \log n)$，查询 $O(1)$（对于可重复贡献的操作，如 max、min、gcd）。不维护的话它甚至不能叫”树”——只是一个二维表格。

倍增（Doubling）是同一思想的另一个应用：预处理”跳 $2^k$ 步后到哪里”，然后用二进制分解回答”跳 $m$ 步后到哪里”。当 $m$ 高达 $10^{18}$ 时，这个技巧尤为重要。

问题的本质

Sparse Table：用”重叠区间”换取 O(1) 查询

线段树查询 $O(\log n)$ 是因为区间不重叠。如果我们允许区间重叠呢？对于 max 操作，$\max(a, b, c) = \max(\max(a, b), \max(b, c))$——重叠一个 $b$ 完全不影响结果。

所以查询 $[l, r]$ 的最大值：找到最大的 $k$ 使得 $2^k \le r - l + 1$，然后答案是 $\max(\text{table}[l][k], \text{table}[r-2^k+1][k])$。两个区间的最大值取 max 就是答案——即使它们重叠了。

倍增：二进制分解”跳步”

假设你站在位置 $x$，每次走到 $f(x)$。问走 $K$ 步后在哪儿？$K$ 高达 $10^{18}$。

预处理 next[x][k] = 从 $x$ 出发走 $2^k$ 步后到达的位置。递推：next[x][k] = next[next[x][k-1]][k-1]。然后对 $K$ 做二进制分解，每次跳 $2^k$ 步。

理论 + 代码

Sparse Table

预处理：table[i][k] = 区间 $[i, i+2^k-1]$ 的最大值。

const int LOG = 20;
int table[MAXN][LOG], lg2[MAXN];

void build(int a[], int n) {
    for (int i = 2; i <= n; i++) lg2[i] = lg2[i/2] + 1; // ① 预计算 log
    for (int i = 0; i < n; i++) table[i][0] = a[i];      // ② 长度 1 的区间
    for (int k = 1; k < LOG; k++)
        for (int i = 0; i + (1 << k) - 1 < n; i++)
            table[i][k] = max(table[i][k-1],              // ③ 前半段
                              table[i+(1<<(k-1))][k-1]);  // ④ 后半段
}

int query(int l, int r) { // 0-indexed, 闭区间
    int k = lg2[r - l + 1];
    return max(table[l][k], table[r-(1<<k)+1][k]); // ⑤ 两个重叠区间取 max
}

逐行解析：

• ① lg2[i] 预计算 $\lfloor \log_2 i \rfloor$，查询时 $O(1)$ 查表。
• ③④ 递推：长度 $2^k$ 的区间 = 两个长度 $2^{k-1}$ 的区间取 max。
• ⑤ 查询：找最大的 $k$ 使得 $2^k \le \text{区间长度}$，两个重叠区间取 max。

倍增法

const int LOG = 60; // 10^18 < 2^60
int next_pos[MAXN][LOG];

void build(int f[], int n) {
    for (int i = 0; i < n; i++) next_pos[i][0] = f[i]; // ① 走 1 步
    for (int k = 1; k < LOG; k++)
        for (int i = 0; i < n; i++)
            next_pos[i][k] = next_pos[next_pos[i][k-1]][k-1]; // ② 走 2^k 步
}

int jump(int x, long long K) {
    for (int k = 0; k < LOG; k++)
        if ((K >> k) & 1)              // ③ K 的第 k 位是 1
            x = next_pos[x][k];         // ④ 跳 2^k 步
    return x;
}

模拟走一遍

$f = [2, 4, 1, 7, 6, 5, 3]$（0-indexed），build next_pos：

next_pos[i][0] = f[i]：从 $i$ 走 1 步到 $f[i]$。 next_pos[i][1]：从 $i$ 走 2 步。例如 next_pos[0][1] = next_pos[f[0]][0] = next_pos[2][0] = 1。

查询：从位置 0 出发走 5 步。$5 = (101)_2$。

• $k=0$：跳 $2^0=1$ 步，从 0 → next_pos[0][0] = 2
• $k=2$：跳 $2^2=4$ 步，从 2 → next_pos[2][2] = ？

需要逐层查。对应 $0 \to 2 \to 1 \to 4 \to 6 \to 3$，第 5 步后位置 3。✓

例题

例题 1：M&A 062 — Teleporter

题目：$N$ 个城镇，城镇 $i$ 的传送门通向城镇 $A_i$。从城镇 1 出发，使用传送门恰好 $K$ 次，到达哪个城镇？

数据范围：$2 \le N \le 2 \times 10^5$，$1 \le K \le 10^{18}$

—— AtCoder Math & Algorithm 062

分析：裸的倍增法。$K$ 高达 $10^{18}$，不能模拟。预处理 next[i][k] = 从城镇 $i$ 出发使用 $2^k$ 次传送门后的位置。1-indexed。

代码：

#include <cstdio>
using namespace std;

const int LOG = 60;
const int MAXN = 200006;
int nxt[MAXN][LOG];

int main() {
    int N;
    long long K;
    scanf("%d%lld", &N, &K);
    for (int i = 1; i <= N; i++) scanf("%d", &nxt[i][0]); // ① 走 1 步
    for (int k = 1; k < LOG; k++)
        for (int i = 1; i <= N; i++)
            nxt[i][k] = nxt[nxt[i][k-1]][k-1]; // ② 递推

    int pos = 1;
    for (int k = 0; k < LOG; k++)
        if ((K >> k) & 1) pos = nxt[pos][k]; // ③ 二进制分解跳步
    printf("%d\n", pos);
    return 0;
}

逐行解析：

• ① nxt[i][0] 就是题目给的 $A_i$，从 $i$ 走 1 步。
• ② 递推：走 $2^k$ 步 = 先走 $2^{k-1}$ 步，再走 $2^{k-1}$ 步。
• ③ 把 $K$ 的二进制表示逐位检查，跳对应的步数。

验证：$N=4, K=5, A=[3,2,4,1]$。路径：1→3→4→1→3→4，第 5 步到 4。✓

---

例题 2：TB A57 — Doubling

题目：$N$ 个洞，蚂蚁在洞 $i$ 的次日移到洞 $A_i$。$Q$ 个查询：从洞 $X_j$ 出发 $Y_j$ 天后在哪个洞？

数据范围：$1 \le N, Q \le 10^5$，$1 \le Y_j \le 10^9$

—— AtCoder Tessoku Book A57

分析：和例题 1 几乎一样，只是输入格式略有不同（1-indexed，多查询）。

代码：

#include <cstdio>
using namespace std;

const int LOG = 30; // 10^9 < 2^30
const int MAXN = 100006;
int nxt[MAXN][LOG];

int main() {
    int N, Q;
    scanf("%d%d", &N, &Q);
    for (int i = 1; i <= N; i++) scanf("%d", &nxt[i][0]);
    for (int k = 1; k < LOG; k++)
        for (int i = 1; i <= N; i++)
            nxt[i][k] = nxt[nxt[i][k-1]][k-1];

    while (Q--) {
        int X; int Y;
        scanf("%d%d", &X, &Y);
        int pos = X;
        for (int k = 0; k < LOG; k++)
            if ((Y >> k) & 1) pos = nxt[pos][k];
        printf("%d\n", pos);
    }
    return 0;
}

逐行解析：

• ① nxt[i][0] 就是题目给的 $A_i$，从洞 $i$ 走 1 天到的位置。
• ② 递推：走 $2^k$ 天 = 先走 $2^{k-1}$ 天，再走 $2^{k-1}$ 天。
• ③ 多查询：对每个查询，把 $Y_j$ 做二进制分解，逐位跳步。$O(Q \log Y)$。

---

例题 3：T90 058 — Original Calculator（★4）

题目：计算器显示 0~99999 的整数。按钮 A：设当前为 $x$，令 $y$ 为 $x$ 各位数字之和，显示 $(x+y) \bmod 10^5$。初始显示 $N$，按 $K$ 次后显示什么？

数据范围：$0 \le N \le 99999$，$1 \le K \le 10^{18}$

—— AtCoder Typical 90 058

分析：状态转移函数 $f(x) = (x + \text{digitsum}(x)) \bmod 10^5$。从 $N$ 出发走 $K$ 步。标准倍增。

代码：

#include <cstdio>
using namespace std;

const int LOG = 60;
const int MAXV = 100000;
int nxt[MAXV][LOG];

int dsum(int x) {
    int s = 0;
    while (x) { s += x % 10; x /= 10; }
    return s;
}

int main() {
    int N;
    long long K;
    scanf("%d%lld", &N, &K);
    for (int i = 0; i < MAXV; i++)
        nxt[i][0] = (i + dsum(i)) % MAXV; // ① 计算走 1 步的转移
    for (int k = 1; k < LOG; k++)
        for (int i = 0; i < MAXV; i++)
            nxt[i][k] = nxt[nxt[i][k-1]][k-1];

    int pos = N;
    for (int k = 0; k < LOG; k++)
        if ((K >> k) & 1) pos = nxt[pos][k];
    printf("%d\n", pos);
    return 0;
}

逐行解析：

• ① dsum(i) 计算各位数字之和。转移函数是 $(i + \text{dsum}(i)) \bmod 10^5$。

验证：$N=5, K=3$。$5 \to 10 \to 11 \to 13$。输出 13。✓

---

例题 4：Sparse Table RMQ

作为 Sparse Table 的演示，我们用一个经典的 RMQ 场景：

场景：给定长度 $N$ 的数组 $A$（不会改变），回答 $Q$ 次区间最大值查询。

方法：Sparse Table 预处理 $O(n \log n)$，每次查询 $O(1)$。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAXN = 100006;
const int LOG = 17;
int table[MAXN][LOG], lg2[MAXN];

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

int main() {
    int N, Q;
    scanf("%d%d", &N, &Q);
    for (int i = 1; i <= N; i++) scanf("%d", &table[i][0]); // ① 读入原始数组
    for (int i = 2; i <= N; i++) lg2[i] = lg2[i/2] + 1;      // ② 预计算 log
    for (int k = 1; k < LOG; k++)                              // ③ 逐层递推
        for (int i = 1; i + (1<<k) - 1 <= N; i++)
            table[i][k] = max(table[i][k-1], table[i+(1<<(k-1))][k-1]); // ④ 两个半段取 max

    while (Q--) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", query(l, r));                          // ⑤ O(1) 查询
    }
    return 0;
}

逐行解析：

• ① table[i][0] 就是原始数组本身（长度 $2^0=1$ 的区间）。
• ② lg2[i] 预计算 $\lfloor\log_2 i\rfloor$，查询时 $O(1)$ 查表而非调用 log。
• ③④ 外层循环 k 是区间长度（$2^k$），内层循环 i 是起点。长度 $2^k$ 的区间 = 两个长度 $2^{k-1}$ 的子区间取 max。
• ⑤ query(l, r)：找最大的 $k$ 使得 $2^k \le r-l+1$，然后两个可能重叠的区间取 max，$O(1)$。

参考文献

教材讲解 — 競技プログラミングの鉄則 第 8 章

• 8.7 B57 Calculator（倍增法 解说，含 dp[d][i] 前計算原理）
• Sparse Table 为课堂延伸内容，教材本体 8.8 节涉及 RMQ 的另解

基础练习 — アルゴリズムと数学 演習問題集

• 062 Teleporter（倍增求周期）【例题】

系统练习 — 競技プログラミングの鉄則

• A57 Doubling（倍增基础）【例题】
• B57 Calculator（各位数字之和+倍增）

实战练习 — 競プロ典型 90 問

• 058 Original Calculator（★4，倍增求周期）【例题】
• 059 Many Graph Queries（★7，倍增+可达性）

---

系列索引

第零章 基础工具

• 00-01 复杂度与暴力枚举
• 00-02 排序
• 00-03 累积和与差分

第一章 搜索技术

• 01-01 二分搜索
• 01-02 双指针与尺取法

第二章 数学基础

• 02-01 整数与整除
• 02-02 素数与筛法
• 02-03 同余与模运算
• 02-04 快速幂与逆元
• 02-05 组合计数
• 02-06 容斥原理
• 02-07 欧拉函数
• 02-08 博弈论基础

第三章 数据结构

• 03-01 栈、队列与单调栈
• 03-02 堆与优先队列
• 03-03 并查集
• 03-04 树状数组
• 03-05 线段树
• 03-06 懒标记线段树
• 03-07 Sparse Table 与倍增
• 03-08 字符串哈希

第四章 图论

• 04-01 图的遍历
• 04-02 最短路—Dijkstra 与 01-BFS
• 04-03 最短路—Bellman-Ford 与 Floyd
• 04-04 拓扑排序
• 04-05 最小生成树
• 04-06 强连通分量与 2-SAT
• 04-07 二分图与网络流
• 04-08 树上问题

第五章 动态规划

• 05-01 DP入门—状态与转移
• 05-02 背包问题族
• 05-03 LIS、LCS与编辑距离
• 05-04 区间DP
• 05-05 状态压缩DP
• 05-06 树形DP与数位DP
• 05-07 矩阵快速幂与线性递推

第六章 贪心

• 06-01 贪心策略与交换论证
• 06-02 区间调度与优化

第七章 字符串

• 07-01 字符串哈希详述
• 07-02 后缀数组

第八章 进阶

• 08-01 卷积与FFT
• 08-02 期望与概率
• 08-03 Zeta / Möbius 变换
• 08-04 计算几何基础
• 08-05 采样与随机化