Algorithm11.7 数据结构 ST表
[TOC]
ST表-可重复贡献问题 // RMQ（Min/Max） // 区间gcd
区间min/max/gcd 区分与线段树 ？？？
https://www.luogu.com.cn/problem/P3865
模版 - ST表
题目大意：得到范围内（Range）最大值（Max）的若干次查询（Query）=>RMQ问题
1、倍增思想，核心就是二倍二倍的获取最大值，类似于二叉树结构的遍历过程，复杂度为O(nlogn)。
maxx[i][j]二维数组：维护的数据结构，表示[i, i+pow(2, j)-1]区间的最大值。=>i表示区间的起点，j表示倍增的倍数。所以在初始化的时候j所需要max的就是两个j-1倍数的区间来比较最大值(其中两个区间的起点分别是i和i+1<<(j-1))，也就是在这个倍增的倍数情况下，需要把起点往后挪的长度。
maxx[i][j] = max(maxx[i][j-1], max[i+(1<<(j-1))][j-1]);
2、查询的时候反向解析
利用query函数来进行解析：先找到该区间对应的倍数，然后再顺着区间的右边界找到对应的查找区间，可以考虑到这个区间不一定是刚好划分好的二倍的区间，所以可以通过拼接子区间来获取最大的
int k = log2(r-l+1);
return max(maxx[l][k], maxx[r-(1<<k)+1][k]);
3、注意数组不要开太大，因为倍增最多也就是21倍，2的21次方这么大的区间长度
#include <iostream>
using namespace std;
#define maxn 1000010
int n, m, a[maxn], maxx[maxn][21], ta, tb; // maxx[i][j]表示[i, i+pow(2, j)-1]的区间的最大值
inline int read()
{
char c=getchar();int x=0,f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
return x*f;
}
// init maxx数组，通过迭代j来2倍率的速度进行初始化=>填补maxx数组
void init() {
for (int i = 1; i <= n; ++i) maxx[i][0] = a[i];
for (int j = 1; j <= 21; ++j)
for (int i = 1; i+(1<<j)-1 <= n; ++i)
maxx[i][j] = max(maxx[i][j-1], maxx[i+(1<<(j-1))][j-1]);
}
int query(int l, int r) {
int k = log2(r-l+1);
return max(maxx[l][k], maxx[r-(1<<k)+1][k]);
}
int main() {
n = read();m = read();
for (int i = 1; i <= n; ++i) a[i] = read();
init();
while (m--) {
ta = read();tb = read();
printf("%d\n", query(ta, tb));
}
return 0;
}
RMQ模版-最大和最小都有
【类似https://www.luogu.com.cn/problem/P2880】
#include <iostream>
using namespace std;
#define maxn 1000010
int n, m, a[maxn], maxx[maxn][21], minn[maxn][21], ta, tb;
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
void init() {
for (int i = 1; i <= n; ++i) {minn[i][0] = a[i]; maxx[i][0] = a[i];}
for (int j = 1; j <= 21; ++j)
for (int i = 1; i+(1<<j)-1 <= n; ++i){
maxx[i][j] = max(maxx[i][j-1], maxx[i+(1<<(j-1))][j-1]);
minn[i][j] = min(minn[i][j-1], minn[i+(1<<(j-1))][j-1]);
}
}
int query_max(int l, int r) {
int k = log2(r-l+1);
return max(maxx[l][k], maxx[r-(1<<k)+1][k]);
}
int query_min(int l, int r) {
int k = log2(r-l+1);
return min(minn[l][k], minn[r-(1<<k)+1][k]);
}
int main() {
n = read();m = read();
for (int i = 1; i <= n; ++i) a[i] = read();
init();
while (m--) {
ta = read();tb = read();
printf("%d %d\n", query_min(ta, tb), query_max(ta, tb));
}
return 0;
}
可重复贡献的例子：区间gcd
https://www.luogu.com.cn/problem/P1890
1、理解init初始化的时候的范围：外层遍历倍数j，内层遍历起点i，保证起点i+上层倍数j的倍增的结果不能爆掉n，此时要考虑的是整体长度，所以是j的倍增，也就是i+(j<<1)-1 <= n
2、利用倍增的二倍过程进行筛选的原理是利用两个下层j-1的来进行比较min/max/gcd，然后再更新上层j。注意起点此时就要考虑的是下层的长度，也就是(1<<(j-1))
#include <iostream>
using namespace std;
#define maxn 1005
int n, m, a[maxn], gcdd[maxn][21], ta, tb;
#include <cmath>
int gcd(int a, int b) {return b>0?gcd(b, a%b):a;}
void init(){
for (int i = 1; i <= n; ++i) gcdd[i][0] = a[i];
for (int j = 1; j <= 21; ++j)
for (int i = 1; i+(1<<j)-1 <= n; ++i)
gcdd[i][j] = gcd(gcdd[i][j-1], gcdd[i+(1<<(j-1))][j-1]);
}
int query_gcd(int l, int r) {
int k = log2(r-l+1);
return gcd(gcdd[l][k], gcdd[r-(1<<k)+1][k]);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
init();
while (m--) {
scanf("%d%d", &ta, &tb);
printf("%d\n", query_gcd(ta, tb));
}
return 0;
}