倍增st表

题目描述

给出n个数，m次询问，给出l,r的最大值/最小值，时间复杂度要求低

code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7, M = 22;
int n, m, f[N][M], lg[N];
void init() {
	for (int j = 1; j <= lg[n]; ++j)
        //每次查找当前长度需要的距离
		for (int i = 1; i <= n; ++i) {
            //我现在在遍历长度，那么你现在肯定要由上一个状态继承
			f[i][j] = f[i][j-1];
            // 你现在并没有越界，所以可以进行两部分的比较
			if (i+(1<<(j-1)) <= n)//当前位置的起始点
				f[i][j] = max(f[i][j], f[i+(1<<(j-1))][j-1]);
		}
}
int query(int x, int y) {
	int s = lg[y-x+1];
    // 你需要找能覆盖当前长度的最小长度
	return max(f[x][s], f[y-(1<<s)+1][s]);//反推起点终点
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 2; i <= n; ++i)
		lg[i] = lg[i>>1] + 1;
    //覆盖长度为i的最短需要的距离,lg2(i)
	for (int i = 1; i <= n; ++i)
		scanf("%d", &f[i][0]);
    //一开始长度为2^0=1的时候，解是自己
	init();
	while (m--) {
		int x, y;
		scanf("%d%d", &x, &y);
		printf("%d\n", query(x, y));
	}
}