倍增与ST表

模版题: https://www.luogu.com.cn/problem/P2880

动画解析: https://www.bilibili.com/video/BV1pTr8BsEgK/

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;
typedef long long ll;
int a[2000000], stmax[60000][600], stmin[60000][600], p1[60000];
int n, m;



int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n >> m;
    
    for (int i=1;i<=n;i++) cin >> a[i];
    // 预处理数据
    p1[1] = 0;
    for (int x=2;x<=n;x++) {
    	p1[x] = p1[x/2] + 1;
    }
    
    for (int i=1;i<=n;i++) {
    	stmax[i][0] = a[i];
    	stmin[i][0] = a[i];
    }
    for (int p=1;1 << p <= n;p++) {
    	for (int i=1;i + (1 << p) - 1 <= n;i++) {
    		int tmp = i + (1 << (p - 1));
    		stmax[i][p] = max(stmax[i][p-1], stmax[tmp][p-1]);
    		stmin[i][p] = min(stmin[i][p-1], stmin[tmp][p-1]);
	}
    }
	
	for (int i=1;i<=m;i++) {
		int a, b;
		cin >> a >> b;
		int k = p(b - a + 1); // 可替换为log2(b - a + 1)
		cout << max(stmax[a][k], stmax[b - (1 << k) + 1][k]) - min(stmin[a][k], stmin[b - (1 << k) + 1][k]) << endl;
	}
    return 0;
}

其中

1 << p

是将p的二进制想右移动一位，即成二。以上代码等价于1 * 2 乘方 p

此外，还要注意何时加1何时减一