深入理解倍增算法与ST表

RMQ问题：给出一个序列，然后多次询问某一个区间的最大值。

一种显然的暴力：每次O(N)遍历，总O(NM)，显然会超时。
ST表：
O(NlogN)对一个序列进行预处理，每次O(1)查询给定区间的最值,总O(NlogN+M)。
思路：
预处理：
令f[j][i]表示区间[j,j+2^i-1]内的最大值，
显然f[i][0]=a[i]
从小到大枚举i从1~20，
有f[j][i]=max(f[j][i-1],f[j+(1<<(i-1))][i-1])
从DP的观点看，是从i-1推出i。
事实上，每次所需处理的区间长度均为上一次的2倍，所以由上一次的区间最值一定可以推出这一次的区间最值。

用线段清晰地表示处理过程
i /已确定答案的区间

求值：
由上图可以看出，其实并没有处理“任意区间”，为什么可以回答任意询问呢？
因为最值具有“可重复贡献的性质”，
只要我们找出两个的区间，它们的并集恰好等于询问区间，则两个区间最值的最值就是询问区间的最值。
具体地：从左端点开始往右找，从右端点往左找
令s=log2(r-l+1)
则ans=max(a[l][s],a[r-(1<<s)+1][s])
理想情况下，两个区间都正好是上图中“已处理的区间”
其他情况下，因为log2是下取整，这样做保证了不会第一个查询超过范围，而第二个范围里-(1<<s)+1的绝对值严格等于2^s-1，恰好到右端点。
另外，s在向下取整时至多不会比真实值小1，则两个区间长度均为l-r+1的一半以上，所以[l,r]一定被完整覆盖。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m,f[200005][21],l,r;
 4 int main(){
 5   cin>>n>>m;
 6   for(int i=1;i<=n;i++)cin>>f[i][0];
 7   for(int i=1;i<=20;i++)
 8     for(int j=1;j+(1<<i)<=n+1;j++)
 9       f[j][i]=max(f[j][i-1],f[j+(1<<(i-1))][i-1]);
10   for(int i=1;i<=m;i++){
11     cin>>l>>r;
12     int s=log2(r-l+1);
13     cout<<max(f[l][s],f[r-(1<<s)+1][s])<<endl;
14   } 
15 }