倍增思想

倍增关注的是指数级跨越（跳过冗余，化线为点）。

倍增依赖的是二进制拆分（任意数字都能唯一分解为 $2$ 的幂的和）。

倍增的核心思想是预处理与动态组合（空间换时间，将线性复杂度降为对数级）。

一、倍增 (Binary Lifting) 核心定义

倍增字面意思是“成倍增长”。假设要走 $K$ 步，一步一步递推要 $O(K)$。倍增法提前存好走 $1,2,4,8,\dots$ 步的结果，查询时把这些跨度拼起来，只需 $O(\log K)$ 的时间。

通俗理解： “走台阶与传送门”。假设要去距离自己 $13$ 步远的地方，普通方法是走 $13$ 次。倍增方法是预先建好各种跨度为 $2$ 的整数次幂的传送门（跨度为 $8, 4, 2, 1$）。只需从大到小挑选：先用跨度 $8$ 的，剩下 $5$ 步；再用跨度 $4$ 的，剩下 $1$ 步；最后用跨度 $1$ 的。原本 $13$ 次的操作，只用了 $3$ 次传送就精准到达。

二、核心应用模型：序列 $K$ 步跳转 (K-step Jump)

剥离树形结构和图论，倍增最纯粹的形态就是在序列上的快速跳跃。

给定一个大小为 $N$ 的数组 $a$，其中 $a[i]$ 表示从位置 $i$ 走 $1$ 步会到达的下一个位置。

核心需求： 面对海量查询，每次询问“从位置 $x$ 出发，走 $k$ 步后最终会停在哪里”。

1. 标准求解算法与模板

下面约定 $n\le10^5$，每个 a[i] 都在 [1,n] 内，查询步数 $0\le k\le10^{18}$，所以处理二进制的第 $0\sim59$ 位就够了。这里 $N$ 管位置个数，$K$ 管步数，别把两个规模混在一起。

f[j][i] 的含义和转移见下一节，这里先看一遍预处理与查询的整体轮廓。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;
int n,m,a[N],f[60][N];
void build(){
    for(int i=1;i<=n;++i)f[0][i]=a[i];
    for(int j=1;j<=59;++j)
        for(int i=1;i<=n;++i)
            f[j][i]=f[j-1][f[j-1][i]];
}
int query(int x,int k){
    for(int j=0;j<=59;++j){
        if((k>>j)&1)
            x=f[j][x];
    }
    return x;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i)cin>>a[i];
    build();
    while(m--){
        int x,k;
        cin>>x>>k;
        cout<<query(x,k)<<'\n';
    }
    return 0;
}

三、核心原理推导 (State Transition & Query)

1. 状态定义

设 f[j][i] 表示从起点 $i$ 出发，精确向前跳跃 $2^j$ 步后到达的位置。

边界条件 f[0][i] 就是从起点 $i$ 跳跃 $2^0 = 1$ 步到达的位置，即原数组直接给出的下一步走向 a[i]。

2. 状态转移方程

跳跃 $2^j$ 步的动作，在空间上可以严格对半拆分为两次连续的跳跃：先向前跳 $2^{j-1}$ 步到达某个中转点，再从中转点继续向前跳 $2^{j-1}$ 步。

代数关系极其严密：$2^{j-1} + 2^{j-1} = 2^j$。

预处理的状态转移方程为：

外层循环枚举指数 $j$，内层循环枚举起点 $i$，自底向上完成所有跨度跳跃航点的建设。预处理时间复杂度为 $O(N \log K)$。

3. 查询的二进制拆分

当面临任意步数 $K$ 时，由于任何一个正整数都能被唯一地表示为若干个不重复的 $2$ 的次幂之和（即二进制表示法），只需将 $K$ 的二进制拆开。

例如 $K = 13$，其二进制为 1101，即 $13 = 2^3 + 2^2 + 2^0 = 8 + 4 + 1$。

遍历 $K$ 的每一位，如果第 $j$ 位是 1，就让当前位置 $x$ 利用预处理好的 f[j][x] 传送阵直接跨越 $2^j$ 步。最终拼合起来恰好是 $K$ 步。单次查询时间复杂度极度压缩至 $O(\log K)$。

四、选学：视角的升维——函数复合与排列的 K 次方

先修要求：理解基础的映射与函数概念。

场景：很多题目并没有明显的“走路”背景，而是给你一个映射规则 $p_i$，问你把这个规则连续应用 $K$ 次后，每个元素会变成什么样。

物理意义：这在数学上叫函数的 $K$ 次复合 $g^k(x)$，在编程里这就是把数组当成函数来执行。如果 $p$ 数组是一个从 $1$ 到 $n$ 的排列（每个数互不相同），它会形成若干个环，这是典型的“置换群”。

降维打击：完全不需要提前学复杂的群论！只要把映射规则 $p_i$ 当作图上走到下一步的 a[i]，然后直接套用倍增模板：f[j][i] = f[j-1][f[j-1][i]]。预处理完后，f[j][i] 就是对 $i$ 连续应用了 $2^j$ 次函数的结果。这种思维转换能秒杀绝大多数“洗牌 $K$ 次”、“序列置换”问题。

五、进阶模型一：倍增维护路径信息（权值与最值）

问题场景：我们不仅要查询 $K$ 步后走到哪，还要问这 $K$ 步过程中，经过的路径总权值或者最大权值是多少。

状态含义：既然位置可以用倍增拆分，路上捡到的金币（权值）同样可以拆分！ 新增灵魂数组 w[j][i]：表示从起点 $i$ 出发，精确跳跃 $2^j$ 步，在路径上收集到的总权值。

关键推导： 跳跃依然是对半拆开，路径收益自然也就是前一半收益加上后一半收益。 状态转移方程非常严谨：

手算小例子： 假设单步得分为权值。我们在一条直线上：1 -> 2 -> 3。 第一步，从 1 走到 2，得分 5，即 w[0][1] = 5，且 f[0][1] = 2。 第二步，从 2 走到 3，得分 8，即 w[0][2] = 8。 我们要算从 1 跳 2 步的得分 w[1][1]。根据推导公式： w[1][1] = w[0][1] + w[0][f[0][1]] = w[0][1] + w[0][2] = 5 + 8 = 13。极其顺畅！

实现要点： 下面按 $K\le 10^9$、单步权值在 $[0,10^9]$ 内来开表：下标 $0\sim29$ 足够，路径和用 long long。不要无脑开到过高的层数，有环时高层的路径和可能先溢出。

在查询 $K$ 步跳转的时候，我们要一边改变位置 x，一边累加权值 ans。注意铁律：必须先吃掉当前跳跃的权值，再真正移动 x 指针！

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;

int n, f[30][N], w[30][N];

void build() {
    // 假设 f[0][i] (下一步位置) 和 w[0][i] (走这1步的收益) 已经在读入时初始化
    // 0 号点作为越界“黑洞”，到达 0 之后再怎么跳都是 0，收益也是 0
    for(int j=1; j<=29; ++j) {
        for(int i=1; i<=n; ++i) {
            f[j][i] = f[j-1][f[j-1][i]];
            // 路径收益 = 前一半收益 + 后一半收益
            w[j][i] = w[j-1][i] + w[j-1][f[j-1][i]];
        }
    }
}

int query_sum(int x, int k) {
    int ans = 0;
    for(int j=0; j<=29; ++j) {
        if((k >> j) & 1) {
            ans += w[j][x]; // 第一步：先把当前这段跳跃的收益吃掉
            x = f[j][x];    // 第二步：再把位置指针真正挪过去
        }
    }
    return ans;
}

signed main() {
    ios::sync_with_stdio(0),cin.tie(0);
    // 测试例子：3个点成环 1->2->3->1，单步收益分别为 10, 20, 30
    n = 3; 
    f[0][1] = 2; w[0][1] = 10;
    f[0][2] = 3; w[0][2] = 20;
    f[0][3] = 1; w[0][3] = 30;
    
    build();
    // 从 1 出发走 4 步：轨迹是 1->2->3->1->2，收益是 10+20+30+10 = 70
    cout << query_sum(1, 4) << '\n'; 
    return 0;
}

六、进阶模型二：倍增找最远合法位置

问题场景：这是倍增最迷人的一种用法。此时步数 $K$ 是未知的！ 题目现在问你：给你一个起点 $x$ 和一个总预算 $M$，问你最多能跳几步，或者能跳到的最远位置在哪。

关键推导： 既然不知道该跳几步，我们就用二进制进行“贪心试探”。 我们从最大的跨度（例如 $2^{29}$）开始往下挨个试探：

• 如果往前跳 $2^j$ 步，发现没有越界且预算还没超，我们就果断吃掉这 $2^j$ 步！扣除对应预算，起点向前挪。
• 如果往前跳 $2^j$ 步发现超预算了，说明这一大步迈得太狠了，我们按兵不动，假装无事发生。 接着继续试探下一个稍小的跨度 $2^{j-1}$。 这就好比用天平称重，先放最重的砝码，如果重了就拿下来，换轻一点的继续试。只要能放上去就一定放。

与答案二分的本质区别： 很多同学遇到“最大合法位置”会本能地想用二分。这两者有啥区别？

• 二分法：猜一个总步数 $mid$。为了验证这个 $mid$ 行不行，你每次都得从头开始走 $mid$ 步。如果在复杂结构上走 $mid$ 步很慢，二分就会直接超时。
• 倍增法：从大到小倒着试探。当试探 $2^j$ 这段路时，我们直接调用预处理好的 w[j][x] 瞬间得知花费，不需要从头走一遍！如果合法，起点就顺势推过去。这相当于边走边二分，全程只向一个方向推进，没有任何回溯重算的浪费。这也是倍增能把校验的时间复杂度也降下来的终极绝招。

实现要点： 这里约定每次有效跳转的花费是 $[1,10^9]$ 内的整数，预算不超过 $10^9$，所以最多走 $10^9$ 步；0 号点表示越界，不是可以走入的节点。

与拼凑 $K$ 的查询不同，试探法必须倒序枚举指数 $j$（从 $29$ 倒着遍历到 $0$），因为必须先试探大跨度，再试探小跨度，才能拼凑出任何想要的步数。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100005;

int n, f[30][N], w[30][N];

void build() {
    for(int j=1; j<=29; ++j) {
        for(int i=1; i<=n; ++i) {
            f[j][i] = f[j-1][f[j-1][i]];
            w[j][i] = w[j-1][i] + w[j-1][f[j-1][i]];
        }
    }
}

// 试探法：从 x 出发，在花费不超过 limit 的前提下，最多能走多少步？
int query_max_steps(int x, int limit) {
    int steps = 0;
    // 灵魂要点：必须倒序枚举！从大步往小步试
    for(int j=29; j>=0; --j) {
        // 如果往前跳 2^j 步没有越界（0表示越界点），且路径总花费没超标
        if(f[j][x] != 0 && w[j][x] <= limit) {
            limit -= w[j][x];       // 霸气扣除额度
            steps += (1LL << j);    // 步数直接累加上 2^j
            x = f[j][x];            // 真正起跳，指针挪过去
        }
    }
    return steps;
}

signed main() {
    ios::sync_with_stdio(0),cin.tie(0);
    n = 3; 
    // 测试例子：一条单向链 1 -> 2 -> 3 -> 0 (越界)
    f[0][1] = 2; w[0][1] = 10;
    f[0][2] = 3; w[0][2] = 20;
    f[0][3] = 0; w[0][3] = 0; 
    
    build();
    
    // 从 1 出发，兜里有 25 块钱预算。
    // 第一步 1->2 花 10 块，剩下 15 块。
    // 第二步 2->3 要 20 块，钱不够了！不跳。
    // 所以最多只能走 1 步，剩余额度 15，停在点 2。
    cout << query_max_steps(1, 25) << '\n'; 
    return 0;
}

七、经典算法思想横向对比