大佬教程收集整理的这篇文章主要介绍了ST表(Sparse-Table 算法)，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
RMQ (Range Minimum/Maximum Query):询问区间内的最小/最大值
具体要求:
出一个 (n) 个元素的数组 (A1 ,A2 , …, An), 设计一个数据结构, 支持查询操作 (query(L, R)), 计算 (min(A_L, A_{L+1}, ..., A_R)), (max(A_L, A_{L+1}, …, A_R))
我们将先把问题以图的方式画出来, 以下
@H_262_28@触控板用的不是很熟所以不是很好看(
对于 (A) 数组中的每一个位置 (i), 我们可以算出 (min(A_i, ..., A_{i+2^{j-1}}-1)) (max同, 后同), 即可令 (d[i][j]) 长度为 (2^j) 的元素中的最小值, 则有 (d[i][j] = min(d[i][j-1], d[i+2^{j-1}][j-1])), (d[i][0] = a[i]).
对于 (query(L,R)), 我们只需要求 (min(d[L][k], d[R-2^k+1][k]))即可.
#include <stdio.h>
#include <iostream>
using namespace std;
int n, m, a[100003];
int d[100003][103];
inline void init() { // 初始化
for (int i = 1; i <= n; i++)
d[i][0] = a[i];
for (int j = 1; (1 << j) <= n; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++) // 注意不能使 i + (1 << j) - 1, 即 d[i][j] 所对应区间的右端点超过 n
d[i][j] = min(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
return;
}
inlinE int quety(int L, int R) { //查询操作
int k = 0;
while ((1 << (k + 1)) <= R - L + 1)
k++;
return min(d[L][k], d[R - (1 << k) + 1][k]);
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
init();
for (int i = 1; i <= m; i++) {
int L, R;
scanf("%d %d", &L, &R);
printf("%dn", quety(L, R));
}
return 0;
}
洛谷的 P3865 【模板】ST 表 与我的代码只有 min 和 max 之差, 可以练习.
先给出一个简单例子
@H_262_28@我字好丑::>_<::
可以发现上图中的节点个数为 8, 答案即为 (d[L][3]).
然后是一个复杂例子
可以发现, 这张图与上张图对比, 多了一个节点, 节点数不再是 (2^p) 的形式, (d[L][3])这个答案并不能覆盖整个区间.
于是可以想到, 能否用两个较大的, 重合的区间覆盖整个区间, 如图中已经画上的黑色波浪和红色波浪, 前者最小值是 (d[L][3]), 后者最小值是(d[L+1][3]), 即(d[R-2^3+1][3]), 整个区间的最小值就是黑色波浪的最小值和红色波浪的最小值中的小者, 即(min(d[L][3], d[R-2^3+1][3])), 并令一值 k.在 k 取值正确的情况下, (query(L,R) = min(d[L][k], d[R-2^k+1][k])).
不难发现, 想要使得两个区间的并集等于区间[L, R], 仅需使得 (2^k <= R-L+1 < 2^{k+1})成立即可.
于是就完成了有关(query(int L, int R))函数的解释.
UVA11235 Frequent values
不是很难, 但是坑点较多.
@H_262_28@写的好丑..
忘记置零
没有进行分类讨论
各种地方的 +1, -1 忘记打
其他的一些永远也想不到的错误
#include <stdio.h>
#include <iostream>
#include <String.h>
using namespace std;
int m, n = 0, l[100003], r[100003], id[100003];
int d[100003][103];
inline void init() {
for (int i = 1; i <= n; i++)
d[i][0] = r[i] - l[i] + 1;
for (int j = 1; (1 << j) <= n; j++)
for (int i = 1; i + (1 << j) - 1 <= m; i++)
d[i][j] = max(d[i][j-1], d[i+(1<<(j-1))][j-1]);
return;
}
inlinE int query(int L, int R) {
int k = 0;
while (1 << (k + 1) <= R - L + 1)
k++;
return max(d[L][k], d[R - (1 << k) + 1][k]);
}
int main() {
int q;
while (~scanf("%d", &m) && m) {
n = 0;
memset(l, 0, sizeof(l));
memset(r, 0, sizeof(r));
memset(id, 0, sizeof(id));
memset(d, 0, sizeof(d));
scanf("%d", &q);
int last = -100003;
for (int i = 1; i <= m; i++) {
int x;
scanf("%d", &X);
if (x != last)
r[n] = i-1, l[++n] = i, last = x;
id[i] = n;
}
init();
while (q--) {
int L, R;
scanf("%d %d", &L, &R);
if (id[L] == id[R]) // 只能分成一部分
printf("%dn", R - L + 1);
else if (id[L] + 2 <= id[R]) // 可以分成三部分
printf("%dn", max(query(id[L] + 1, id[R] - 1), max(r[id[L]] - L + 1, R - l[id[R]] + 1)));
else // 只能分成两部分
printf("%dn", max(r[id[L]] - L + 1, R - l[id[R]] + 1));
}
}
return 0;
}
以上是大佬教程为你收集整理的ST表(Sparse-Table 算法)全部内容，希望文章能够帮你解决ST表(Sparse-Table 算法)所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。