学习了 ST表
这个高级的东西。。
于是乎来发一些理解和题解以便以后复习。
什么是ST表
ST表的功能很简单:
它是解决RMQ
问题(区间最值问题)的一种强有力的工具。
它可以做到$O(nlogn)$预处理,$O(1)$查询最值(ohhhhhhhh)
实现
怎么做到的呢,它运用了倍增
的思想。
拿最大值来说我们用$Max[i][j]$表示,从$i$位置开始的$2^j$个数中的最大值,例如$Max[i][1]$表示的是$i$位置和$i+1$位置中两个数的最大值(也就是说当前位置是被包含进$2^j$个数去的)
那么转移的时候我们可以把当前区间拆成两个区间并分别取最大值(注意这里的编号是从$1$开始的)

查询的时候也比较简单
我们计算出$log_2{lenth}$,然后对于左端点和右端点分别进行查询,这样可以保证一定可以覆盖查询的区间

所以就有了这两个边界,$[l,l+2^k-1]$, $[r-2^k+1,r]$
至于为什么会是$[r-2^k+1,r]$,你只要设左端点为$x$, 并且$x$满足$x + 2^k - 1 = r$, 然后就可以推出来了。
例题和代码
给定一个长度为 $N$ 的数列,和 $M$ 次询问,求出每一次询问的区间内数字的最大值。
上代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
| #include <bits/stdc++.h> #define MaxN 100000 + 9 #define LogN 17
using namespace std;
int f[MaxN][LogN], n, m;
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; }
int ask(int l, int r) { int len = log2(r - l + 1); return max(f[l][len], f[r - (1 << len) + 1][len]); }
int main() { n = read(); m = read(); for (int i = 1; i <= n; ++i) f[i][0] = read();
for (int j = 1; j <= 21; ++j) for (int i = 1; i + (1 << j) - 1 <= n; ++i) f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]); int a, b; for (int i = 1; i <= m; ++i) { a = read(); b = read(); printf("%d\n", ask(a, b)); } return 0; }
|
嗯,没有四倍经验。
peace~