倍增

问题引入

Q1: 给定一个正数x，已知x一定可用m个二进制位表示，从高位到低位打印x每一位的状态

从数二进制位左往右第i位计算1<<i，让原数与其相减，若结果小于0则不减，并将该位状态标记为0，若大于0则减去，并将该位状态标记为1

如数101，二进制为0001100101，

1<<9为512>101，不减，第九位状态为0

1<<8为256>101，不减，第八位状态为0

1<<7为128>101，不减，第七位状态为0

1<<6为64<101，减成37，第六位状态为1

1<<5为25<32，减成5，第五位状态为1

以此类推

Q2: 给定一个正数x，打印<=x的最大的2的幂是2的几次方，注意防溢出

若x=13，则\(2^3=8\)最接近13，输出3

若x=16，则\(2^4=16\)最接近16，输出4

溢出：若x非常接近INT_MAX，则每次从\(2^{p-1}\leq x\leq2^p\)时很有可能溢出

解决方案：当\(2^p\leq \frac{x}{2}\)时就让p++

int q2(int x){
    int power = 0;
    while(1<<power)<=(x>>1){
        power++;
    }
    return power;
}

倍增算法

线段上有n个点，给定每个点i往右边跳1步能最远覆盖的点jump[i]

已知从任意点出发都能到达最后的点，并且在i<j时，必定有jump[i]<=jump[j]

如何构建一张表可以查询从任意点i出发，任意跳\(2^p\)步，最远能到达的点

如何快速计算任意两点之间，最少跳几步能到达

如该表，行代表p，表示\(2^p\)次方内对应点是否能到达，列代表点i

初始jump[i]填入第一列，即st[i][0]=jump[i]，后面列的填充满足转移方程st[i][p]=st[st[i][p-1]][p-1]，即跳\(2^p\)内能到达的可以转化为从\(2^{p-1}\)跳\(2^{p-1}\)内能到达

该表列最多\(\log_2n\)列

这就是ST表，我们利用ST表从x到y跳跃的过程中，先从最大步长开始，每次减少一半尝试，最后得到答案

假设计算17到77至少要多少步

我们知道至多需要60步，而60可以用六个二进制位表示

从左往右，让17往右跳\(2^i\)步，看对应数值大于还是小于77，大于则该位标0，小于则标1，且将步数转为49

最后需要的是逼近77的结果，如最后到达了73，再加一步就能到达77

例-倍增跳跃

P4155 [SCOI2015] 国旗计划

题意：给定m个点，编号1-m，所有点围城一个环，i号点顺时针到达i+1号点，最终m号点顺时针回到1号点

给定n条线段，每条线段(a,b)表示线段顺时针从a到b

保证所有线段可以把整个环覆盖，且线段间可能重合但一定互不包含

返回长度为n的结果数组ans，ans[x]表示一定选x号线段下，至少选几条线段能覆盖整个环

我们将环展开成条进行计算，即每次寻找包含在内且尽量靠右的线段跳跃，寻找离转一圈后的起始点所在的最近的线段

如从A开始，需要经过A->B->D才能到达10(2)点，故需要三条线段覆盖

构建时只需要看第i个点所在线段的末尾是哪个即可，表示一步内从i可以跳到末尾

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
struct node{
  int idx;
  int s,e;
}line[2*N];
int n, m, power;
vector<vector<int>> st;
vector<int> ans;
// 将环状展开为线性
int lgp(int n){
  int ans = 0;
  while((1<<ans)<=(n>>1)){
    ans++;
  }
  return ans;
}
void build(){
  /*如C(6,1),m=8
  * 有1 2 3 4 5 6 7 8 9 10 11 ...
                      1  2  3...
    故转化后的C是(6,9)
  */
  for (int i = 1;i<=n;i++){
    if (line[i].s>line[i].e){
      line[i].e+=m;
    }
  }
  // 按起始点排序
  sort(line+1,line+1+n,[&](const node a, const node b){return a.s<b.s;});
  // 对点在线性上进行复制即 A B C D A' B' C' D'
  for(int i =1;i<=n;i++){
    line[i+n].idx = line[i].idx;
    line[i+n].s = line[i].s+m;
    line[i+n].e = line[i].e+m;
  }
  // 新线段数量
  int e = n<<1;
  // 寻找跳一步的最大值, 应满足下一条线段开头<=当前线段结尾
  /*如线段开头如下
  3
    34 
      56
        89
          102
  到102就超过了结尾，故选择到89
  */
  for (int i =1, j = 1;i<=e;i++){
    while(j+1<=e&&line[j+1].s<=line[i].e){
      j++;
    }
    st[i][0]=j;
  }
  // 倍增
  for (int p = 1; p<=power; p++){
    for (int i = 1;i<=e;i++){
      st[i][p]=st[st[i][p-1]][p-1];
    }
  }
}
int jump(int i){
  // i号线段的目标点是line[i].s+m
  int tar = line[i].s+m,cur = i, next, ans = 1;
  for(int p = power; p>=0;p--){
    next = st[cur][p];
    if (next!=0&&line[next].e<tar){
      ans+=1<<p;
      cur = next;
    }
  }
  return ans+1; // 计算的是小于目标点，+1即为到达 

}
void solve() {
  
  cin >> n >> m;
  
  for(int i =1;i<=n;i++){
    line[i].idx = i; 
    cin >> line[i].s >> line[i].e;
  }
  power = lgp(n);
  st = vector<vector<int>>(2*n+1, vector<int>(power+1,0));
  ans = vector<int>(n+1,0);
  build();
  for (int i = 1;i<=n;i++){
    ans[line[i].idx] = jump(i);
  }
  for (int i = 1;i<=n;i++) cout << ans[i]<<' ';

}
int main()
{
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  int tomorin=1;
  //cin >> tomorin;
  while (tomorin--) solve();
  return 0;
}

例-RMQ问题

P2880 [USACO07JAN] Balanced Lineup G

仍然构造一个st表，表示覆盖范围内对应的最大值

对于状态转移，每次的最大值一定在前一个区间(\(i\to2^{p-1}\))与当前区间(\(i+2^{p-1}\to2^{p-1}\))

对于查询，寻找最接近区间长度的一个2的p次幂，取从起点往后跳\(2^p\)长度与从终点往前跳\(2^p\)长度两者最大值的最大值

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> PII;
const int N = 2e5 + 10;
const double pi = acos(-1.0);
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
int n,m;
vector<vector<int>> dp1;
vector<vector<int>> dp2;
int query1(int l, int r){
  int j = (int)log2(r-l+1);
  return max(dp1[l][j],dp1[r-(1<<j)+1][j]);
}
int query2(int l, int r){
  int j = (int)log2(r-l+1);
  return min(dp2[l][j],dp2[r-(1<<j)+1][j]);
}
int main()
{
  ios
  cin >> n >> m;
  dp1 = vector<vector<int>> (n,vector<int>(log2(n)+5,0));
  dp2 = vector<vector<int>> (n,vector<int>(log2(n)+5,0));
  vector<int> arr(n);
  for (int i = 0;i<n;i++) cin >> arr[i];
  for (int i = 0;i<n;i++) {
    dp1[i][0] = arr[i];
    dp2[i][0] = arr[i];
  } 
  for (int j = 1;j<=log2(n);j++){
    for (int i = 0; i+(1<<j)-1<n;i++){
      dp1[i][j] = max(dp1[i][j-1],dp1[i+(1<<(j-1))][j-1]);
      dp2[i][j] = min(dp2[i][j-1],dp2[i+(1<<(j-1))][j-1]);

    }
  }
  int l,r ;
  while (m--){
    cin >> l >> r;
    cout << query1(l-1,r-1)-query2(l-1,r-1)<<endl;
  }
  return 0;
}

树上倍增

在树结构中也可以实现倍增查找某节点任意层祖先

建立每个节点的深度表

使用st[i][p]指代节点i往上走\(2^p\)步来到哪个祖先，其中st[i][0]是i的父节点

则倍增思想可得st[i][p]=st[st[i][p-1]][p-1]

此时给定任意节点，就可以快速查询i节点的祖先中位于第s层的祖先节点编号

适用范围

适用于可重复贡献问题

即若A与B区间有可能重叠的部分，但不影响A+B区间的答案

如RMQ，gcd，按位与，按位或等都可以使用st表高效解决

优势：构建过程复杂度\(O(n\log n)\)，单次查询\(O(1)\)

劣势：静态维护，需要空间大，维护信息有限

红魔咖啡馆

【算法】倍增

倍增