学习笔记（二）区间问题

一、ST表（RMQ或RGQ问题等）

ST算法处理静态空间的RMQ问题效率相当高，预处理时间复杂度 O(nlogn) ，查询时间复杂度 O(1)。思路同莫队算法类似，同为分块+处理，但是ST完全不支持修改，如果只有查询，ST查询效率远高于莫队。

思路：DP预处理（倍增法）+贪心查询

首先，ST需要分块，通过倍增思路分块。第一组全分为长度为1的块，第二组全分为长度为2的块，第三组长度为4，倍增地以此类推。注意这里的分块每个块之间不是完全互斥的，和归并排序中的分组完全相反，这里的分块是分别以每个元素为头找到长度为2^(组数-1) 的块，只要块的尾没到数组的结尾，就把每个元素都找到这样的块。如此，总共需要logn个块，用二维数组存储，应该类似于 dp[logn][n] 这样，dp[i][j] 代表第i+1组中以j为首元素的块，而记载的答案自然为要找的最大值或最小值。

然后，分块思路和存储方式找到了，第一组即 dp[0][j] 自然为原数组。通过转移方程:

dp[i][j]=min{dp[i-1][j],dp[i-1][j+2^(i-1)]}

递推得到全部的信息。转移方程代表第i+1组以j为首元素的块的最小值为上一组可以将其平分的两个块最小值的最小值。

因为最值是符合贪心的，所以只要两个小区间能完全覆盖住大区间（两个小区间重叠也可以），那么就可以贪心的递推。

最后便是如何查询了，按照上述所言，对于L到R之间的最值查询，len=R-L+1，只要找到两个小块重叠刚好完全覆盖这个长度就好，小块的长度x满足 x<=len<=2x 就好，即小块在第log(len)+1组。令k=log(lR-L+1)，那么答案就出来了：

ans=min{dp[k][L],dp[k][R-2^k+1]}

eg.洛谷P2880

附链接https://www.luogu.com.cn/problem/P2880

#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define rep(i,l,r) for(register int i=l;i<=r;i++)
using namespace std;

const int N = 5e4 + 5;
const int INF = 0x3fffffff;
const double eps = 1e-6;
typedef long long ll;
const int modp = 1e6 + 37;

inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		if (ch == '-')
			f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + ch - 48;
		ch = getchar();
	}
	return x * f;
}

int n, q;
int l, r;
int Log[N];
int dp1[100][N];
int dp2[100][N];

void init() {
	Log[0] = -1;
	rep(i, 1, n) Log[i] = Log[i >> 1] + 1;
	rep(i, 1, Log[n]) {
		rep(j, 1, n) {
			if (j + (1 << i) - 1 <= n)
				dp1[i][j] = min(dp1[i - 1][j], dp1[i - 1][j + (1 << (i - 1))]);
		}
	}
	rep(i, 1, Log[n]) {
		rep(j, 1, n) {
			if (j + (1 << i) - 1 <= n)
				dp2[i][j] = max(dp2[i - 1][j], dp2[i - 1][j + (1 << (i - 1))]);
		}
	}
}

void solve() {
	int mina, maxa;
	int k = Log[r - l + 1];
	mina = min(dp1[k][l], dp1[k][r - (1 << k) + 1]);
	maxa = max(dp2[k][l], dp2[k][r - (1 << k) + 1]);
	cout << maxa - mina << endl;
}

int main() {
	ios::sync_with_stdio(0), cout.tie(0), cin.tie(0);
	n=read();
    q=read();
	rep(i, 1, n)  dp1[0][i] = dp2[0][i] = read();
	init();
	while (q--) {
		l = read();
		r = read();
		solve();
	}
	return 0;
}

同理，求取区间最大公约数问题一样解法。对于离线无需维护数组时用ST算法时间复杂度短且非常好写（只需记住两个dp转移方程就好）。