STtable

ST表

P3865 【模板】ST 表 && RMQ 问题 - 洛谷 | 计算机科学教育新生态

静态区间最大值
给定一个长度为 N 的数列，和 M 次询问，求出每一次询问的区间内数字的最大值。
输入:
第一行包含两个整数 N,M，分别表示数列的长度和询问的个数。
第二行包含 N 个整数（记为 ai ），依次表示数列的第 i 项。
接下来 M 行，每行包含两个整数 li,ri，表示查询的区间为 [li, ri]

8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8

输出

9
9
7
7
9
8
7
9

例如数据，9 3 1 7 5 6 0 8，生成ST表为，其中第i行表示每个数后面\math-container{2\power{i}}个数的区间最大值。
例如i=2，那么就是每个数为基准，长度为4的区间最值。

下标j	1	2	3	4	5	6	7	8
原始i=0	9	3	1	7	5	6	0	8
i=1	9	3	7	7	6	6	8
i=2	9	7	7	7	8
i=3	9

倍增和动规
$a[i][j]=max(a[i-1][j],a[i-1][j+(1≪i-1)])$，1左移一位是2
查询时，例如要查询3到7区间最值，我们先计算这个区间包含几个元素，7-3+1=5个元素，再计算5对应的是2的2次方，那么可知答案就是在ST表的第二行，$a[2][3]$表示3为起点的4个元素的最大值，那么就是3-6区间，另外一个区间终点为7，那么起点是7-4+1，即4-7区间的4个元素，所以求$a[2][3]$和$a[2][4]$两个区间即可。
建表是$nlogn$的复杂度，查询是1的复杂度
可用AC

#include<bits/stdc++.h>
using namespace std;

int n, m, x, y, a[20][100005], len;
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)scanf("%d", &a[0][i]);
    
    len = log2(n);
    
    for(int i = 1; i <= len; i++)
        for(int j = 1; j <= n - (1 << i) + 1; j++)
            a[i][j] = max(a[i-1][j], a[i-1][j+(1<<i-1)]);
    
    for(int i = 1; i <= m; i++){
        scanf("%d%d", &x, &y);
        len = log2(y-x+1);
        printf("%d\n", max(a[len][x], a[len][y-(1<<len)+1]));
    }
    return 0;
}