倍增 st表 RMQ问题

本章我们来谈谈，倍增 && st表 && RMQ问题。

倍增

        倍增即成倍增长。是指我们在进行递推时，如果状态空间很大，线性递推无法满足时空要求，此时可以考虑成倍增长的方式，只递推状态空间在2的整数次幂位置上的值作为代表，其他值可以通过“任意整数可以表示成若干个 的次幂项的和”这一性质得到。

        其实纯倍增的题

ST表

ST 表（Sparse Table，稀疏表）是用于解决可重复贡献问题的数据结构。

例如：给定个数，n个询问，对于每个询问，求解区间 [l, r] 的极值（如最大值，最小值...）。

但是其实对这种朴实无华的DP，可以用倍增去优化。

就相当于把前一半和后一半取一个最小值，f(i,j)表示第[i,i+2^j-1]之间的最小值，如果理解不了可以想2^0-1 = 0，那么[i,i+0]就是a[i]本身那个数，后面同理....

模板代码

见Acwing:1273. 天才的记忆

#include<bits/stdc++.h>
using namespace std;const int N  = 2*1e5+10,M = 18;int n,m;
int w[N];
int f[N][M]; //运用倍增的思想，f(i,j)表示从i开始到i到i+2^j的区间最大值void init(){for(int j = 0; j < M; j++){for(int i = 1; i+(1 << j)-1 <= n; i++){if(!j) f[i][j] = w[i];//i——i+2^j区间最大值可以转化为i——i+2^(j-1)，和i+2^(j-1)——i+2^(j-1)+2^(j-1)中间虽然有重复部分但是取最大值else f[i][j] = max(f[i][j-1],f[i+(1 << (j-1))][j-1]);}}
}int query(int l,int r){int len = r-l+1;int k = log(len)/log(2);return max(f[l][k],f[r-(1 << k)+1][k]);
}int main(){cin >> n;for(int i = 1; i <= n; i++) cin >> w[i];init();cin >> m;while (m -- ){int l, r;cin >> l >> r;cout << query(l,r) << endl;}return 0;
}