25.倍增与稀疏表

发表于 2025-04-05 更新于 2025-04-10 分类于 ACM ， ACMCOURSE

倍增与稀疏表（ST表）

倍增思想的核心在于通过预处理每个状态的跳跃步长（如2的幂次），将线性时间的操作优化为对数时间。其关键在于构建一个跳跃表，每个位置存储跳跃不同\(2^k\)步后的结果。对于多次跳跃问题，将总步数分解为若干2的幂次之和，逐次跳跃即可高效求解。

倍增思想

纸币有1元、5元、10元、50元、100元的面额，用于方便地凑成任意金额。

在编程思维中，\(2^0, 2^1, 2^2, \dots 2^k\) 可以方便地凑成任意 \(2^{k+1}\) 以内的数（更大的也能凑，但是没那么方便快捷），甚至每个额度只需要出现一次。

随便考虑一个数： \(12\)，它的二进制形式是 1100，二进制的每一位都对应一个\(2^{x}\)，即可以由若干个不重复的\(2^{x}\)凑成。每个整数都可以表达成二进制，所以以上结论显然。

在一些问题中，解存在某种特定关系，或许能允许我们以相对较小的代价预处理出变量（或偏移量）为 \(2^0, 2^1, 2^2, \dots 2^k\) 的结果，从而快速地拼凑任意变量（或偏移量）对应的结果，这就是倍增思想。

例：变化的数

一个数\(a\)，每变化一次，就增加 \(\lfloor \max (|sin(a)|, |cos(a)|) * 20 \rfloor\).

用C语言可以这样完成变化：

1
2
3

int Nexa(int a) {
    return a + (int)(std::max(fabs(sin(a)), fabs(cos(a))) * 20);
}

求它变化 \(m\) 次的值.

第一行数据组数 \(1 \leq t \leq 5 * 10^{4}\)，接下来 \(t\) 行数据，每行 \(1 \leq a, m \leq 5 * 10^{4}\) 表示将 \(a\) 变化 \(m\) 次.

输出

如果\(m\)步慢慢模拟，\(t\)组数据每组\(m\)步就超时了。

如果有每个点走\(2^{0},2^{1},\dots\)步能到达的地方的信息，那么走\(m\)步就会减少到走 \(log_{2}m\)步。

这不仅需要知道第 1 个点的各\(2^i\)步到达位置，而是要知道每一个点的各个\(2^i\)步到达的位置

如下图，一个点的绿、蓝、红、紫线路对应\(2^{0},2^{1},,2^{2},2^{3}\) 步

如果想从起点走 6 步，就先走 1 步红线，到达一个点，然后需要知道这个点的 1 步蓝线，到达目的地。

只要知道所有点的所有\(2^{0},2^{1},,2^{2},\dots\) 步能到达的位置，就可以在 \(log_{2}m\)时间快速计算从任意点出发走\(m\)步到达的位置。

预处理这个信息也有技巧：

从每个点出发走 \(1\) 步能到的地方，用一个循环处理出来；
从每个点出发走 \(2\) 步能到的地方，可以由它走\(1\)步到某个点，该点再走\(1\)步到达，而每个点的\(1\)步到达位置此时已知；
从每个点出发走 \(4\) 步能到的地方，可以由它走\(2\)步到某个点，该点再走\(2\)步到达，而每个点的\(2\)步到达位置此时已知；
……

以上每一步都遍历一遍所有点，共遍历 \(k\) 次，\(k\) 就是需要预处理的最大的 \(2^{k}\) 步的 \(k\)，假设点个数是 \(n\)，\(2^k\approx n\)，所以这个预处理过程是\(O(nlogn)\)的。

回到题目，一个数\(a\)，每变化一次，就增加 \(\lfloor \max (|sin(a)|, |cos(a)|) * 20 \rfloor\)，它每次至多增加\(20\)，由于\(1 \leq a, m \leq 5 * 10^{4}\)，那么这道题最大范围就是 \(5 * 10^4 + 20 * 5 * 10^4 \approx 10^6\)

预处理这样做

const int maxa = 2e5 + 1e4 + 10;
const int maxmt = 22;
int mt[maxa][maxmt];    // maxa 表示起点的可能性数， maxmt 表示最多处理到 2^maxmt 步

void InitMt() {
    for(int j = 1; j < maxa; j ++) {
        mt[j][0] = Nexa(j);     // 初始化走 1 步（即 2^0 步）的值
    }
    for(int i = 1; i < maxmt; i ++) {       // 枚举步长，i 表示 2^i 步
        for(int j = 1; j < maxa; j ++) {    // 枚举起点
            // 利用 2^{i-1} 的信息推算每个 j 位置走 2^i 步的值
            if(mt[j][i - 1] >= maxa) {
                break;  // 超出题目可能的范围，这部分不用计算
            }
            // 位置 j 出发走 2^i 步到的位置，可以从 mt[j][i - 1] 出发走 2^{i-1} 步到达
            // mt[*][i - 1] 已由上一轮循环计算好了
            mt[j][i] = mt[mt[j][i - 1]][i - 1];
        }
    }
}

那么 \(a\) 出发走 \(m\) 步，就可以拆解成走 \(m\) 的各个二进制位对应的步数。

比如 \(m = 7\)，它的最高二进制位就是第 \(\lfloor log_{2}7 \rfloor=2\) 位，第一步就可以走 \(2^2\) 步，对应预处理的表就是 mt[a][2] ，表示从 \(a\) 出发走 \(2^{2} = 4\) 步到达的位置。

更新位置a = mt[a][2]，准备走下一步，那么还剩下 \(7 - 2^2 = 3\) 步，从刚到达的位置出发，进行下一轮计算。

二进制计算有一些加速的 __builtin_*** 函数可以用，这里可以代替 (int)log2(x) 得到更好性能。

int Fastlog(int x) {
    // log2函数较慢，利用 int 二进制位数高效地计算 (int)log2(x)
    return 31 - __builtin_clz(x);
}
while(m) {
    int lg = Fastlog(m);    // 找距离 m 最近的 2^{lg} 的 lg
    a = mt[a][lg];          // 走 2^{lg} 步
    m -= 1 << lg;           // 减去走过的步数，位运算 1<<lg 就是2^{lg}
}

完整代码如下

// 变化的数
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<algorithm>

const int maxa = 2e5 + 1e4 + 10;
const int maxmt = 22;
int mt[maxa][maxmt];

int Nexa(int a) {
    return a + (int)(std::max(fabs(sin(a)), fabs(cos(a))) * 20);
}

void InitMt() {
    for(int j = 1; j < maxa; j ++) {
        mt[j][0] = Nexa(j);     // 初始化走 1 步（即 2^0 步）的值
    }
    for(int i = 1; i < maxmt; i ++) {       // 枚举步长，i 表示 2^i 步
        for(int j = 1; j < maxa; j ++) {    // 枚举起点
            // 利用 2^{i-1} 的信息推算每个 j 位置走 2^i 步的值
            if(mt[j][i - 1] >= maxa) {
                break;  // 超出题目可能的范围，这部分不用计算
            }
            mt[j][i] = mt[mt[j][i - 1]][i - 1];
        }
    }
}
int Fastlog(int x) {
    // log2函数较慢，利用 int 二进制位数高效地计算 (int)log2(x)
    return 31 - __builtin_clz(x);
}
int main() {
    int t, a, m;
    InitMt();
    for(scanf("%d", &t); t --; ) {
        scanf("%d%d", &a, &m);
        while(m) {
            int lg = Fastlog(m);    // 找距离 m 最近的 2^{lg} 的 lg
            a = mt[a][lg];          // 走 2^{lg} 步
            m -= 1 << lg;           // 减去走过的步数，位运算 1<<lg 就是2^{lg}
        }
        printf("%d\n", a);
    }
    return 0;
}

稀疏表

稀疏表用于解决可重复贡献问题。

对于 \(a<b\)， \([l, b]\)区间、\([a, r]\)区间以及\([l, r]\) 区间的一些计算：

能重复贡献示例：区间最大值，\([l, b]\) 的最大值与 \([a, r]\) 最大值较大的那个同时也是 \([l,r]\) 的最大值， \([a,b]\) 这个区间在最大值问题上就能重复贡献。
不能重复贡献示例： \([l, b]\) 的和与 \([a, r]\) 的和相加，不等于 \([l, r]\) 的和，所以区间和就不能重复贡献。

                        [a,r] 
             /-------------^-------------\
l            a            b               r
-------------------------------------------
\___________ ____________/
            V
          [l,b]

区间最大/最小值（Range Maximum/Minimum Query, RMQ）是典型的可重复贡献问题。

这个问题可以用倍增思想加速查询，预处理好每个点作为起点，它加\(2^0, 2^{1}, 2^{2},\dots\)为终点的区间解，那么对于任意 \([l, r]\) 的查询，设 \(b\) 为 \(b = l + 2^{k} <= r\) 能达到的最大值， \(a\) 为 \(a + 2^{k} = r\) 的值，那么 \([l, b]\) 和 \([a, r]\) 就是 \([l, l + 2^{k}]\) 和 \([r - 2^{k}, r]\)，只要这个问题可重复贡献，这两个预处理过的答案合起来就是 \([l, r]\) 的解。

预处理的过程也是倍增思想来。

例：多次查询区间最大值

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

输入

8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8

输出

#include<cstdio>
#include<cstring>
#include<cmath>
const int maxn = 1e5 + 10;
int n, m, a[maxn], st[maxn][22];   // 起点最大 maxn，预处理到  maxn + 2^{20}
void InitSt(int n) {
    for(int j = 1; j <= n; j ++) {
        st[j][0] = a[j];    // 左闭右开区间理解， [j, j + 1) 就是长为 1 的区间
    }
    for(int i = 1; i <= 22; i++) {
        for(int j = 1; j <= n - (1 << (i - 1)); j ++) {
            // [j, j + 2^{i-1}) 与 [j + 2^{i-1}, j + 2^{i}) 合并 得到 [j, j + 2^{i}]
            st[j][i] = std::max(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
        }
    }
}
int Fastlog(int x) {
    return 31 - __builtin_clz(x);
}
int Query(int l, int r) {
    // 求左闭右开区间 [l, r)
    int k = Fastlog(r - l);
    return std::max(st[l][k], st[r - (1 << k)][k]);
}
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    InitSt(n);
    while(m--) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", Query(l, r + 1));
    }
    
    
    return 0;
}