倍增与ST表学习笔记

Baltic 菠萝的海

2026-05-26 21:19:33

发布于：上海

8阅读

0回复

0点赞

平衡的队列

寻求不固定区间内最大值和最小值的差值。

预处理以每一个位置为开头，长度为 $2^0,2^1,…，2^{log_2n}$ 的所有区间最值。
只考虑最大值，用 $f[i][j]$ 表示 $h_i，h_{i+1}，…，h_{i+2^j-2}，h_{i+2^j-1}$ 中的最大值，用递推的方式计算所有的 $f$ ，转移为： $f[i][j]=max(f[i][j-1],f[i+2^{j-1}][j-1])$ 。预处理时间复杂度 $O(nlog_2n)$

接下来是查询。设需要查询最大值的区间为 $[l,r]$ 。记区间长度为 $L$ ，则该区间可以拆分成 $O(log_2L)$ 的小区间。将 $L$ 二进制拆分，从 $L$ 开始向后跳，每次跳拆出一个2的幂的个数，就可以拼凑出整个区间。

单次查询时间复杂度 $O(log_2n)$ 。

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int a[N];
int f[N][30],f1[N][30];
int main(){
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)f[i][0]=f1[i][0]=a[i];
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i<=n-(1<<j)+1;i++){
			f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
		}
	}
    for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i<=n-(1<<j)+1;i++){
			f1[i][j]=min(f1[i][j-1],f1[i+(1<<j-1)][j-1]);
		}
	}
	for(int i=1;i<=q;i++){
		int a,b;
		cin>>a>>b;
		int len=log2(b-a+1);
		cout<<max(f[a][len],f[b-(1<<len)+1][len])-min(f1[a][len],f1[b-(1<<len)+1][len])<<'\n';
	}
	return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论