RMQ 倍增法 求解读……

Question

数列区间最大值 （RMQ入门）
题目描述:
输入一串数字，然后再给你M个询问，每次询问给你两个数x,y，要求你说出从x到y这段区间内的最大数。
输入格式:
一个整数N表示数字的个数，一个数M，表示要询问的次数。
接下来一行为N个数。
接下来M行，每行都有两个整数x和y。
输出格式:
共M行，每行输出一个数。
样例输入:
10 2
3 2 4 5 6 8 1 2 9 7
1 4
3 8
样例输出:
5
8
提示:
1<=n<=100000,1<=m<=1000000
时间限制: 1000ms
空间限制: 256MB

正解我已经在网上找到了，但看不懂，说是倍增法，求解读……

#include<bits/stdc++.h>
using namespace std;
int n,m,f[100001][17],two[100001];
int query(int x,int y){
    int i=two[y-x+1];
    return max(f[x][i],f[y-(1<<i)+1][i]);
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>f[i][0];
    for(int i=2;i<=n;i++){
        if(i&i-1)two[i]=two[i-1];
        else two[i]=two[i-1]+1;
    }
    for(int i=1;i<=two[n];i++){
        for(int j=1;j+(1<<i)-1<=n;j++){
            f[j][i]=max(f[j][i-1],f[j+(1<<i-1)][i-1]);
        }
    }
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        cout<<query(x,y)<<'\n';
    }
    return 0;
}

Answer 1

你去查一下st表