寂静的角落 星空在前,路在脚下
稀疏表 Sparse Table, ST
发布于: 2021-04-04 更新于: 2021-04-07 分类于: 数据结构 阅读次数: 

$\color{Green}code - oi$

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
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
const int logn = 21, maxn = 2e6+5;
int f[maxn][logn + 1], lg[maxn + 1];
template <typename T = int>
inline T iread(void) {
T n = 0;
register char ch = getchar();
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) n = (n << 3) + (n << 1) + (ch ^ 48), ch = getchar();
return n;
}
inline void makelog(void) {
lg[1] = 0;
lg[2] = 1;
for (register int i = 3; i < maxn; ++i) lg[i] = lg[i >> 1] + 1;
}
int n, m, l, r, s;
int main() {
n = iread(), m = iread();
makelog();
for (register int i = 1; i <= n ; ++i) f[i][0] = iread();
for (register int j = 1; j <= logn; j++)
for (register int i = 1; i + (1 << j) - 1 <= n; i++)
f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
for (register int i = 1; i <= m; ++i) {
l = iread(), r = iread();
s = lg[r - l + 1];
printf("%d\n", max(f[l][s], f[r - (1 << s) + 1][s]));
}
return 0;
}

$\color{Green}code - poject$

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
/*
lb() 为二进制对数
*/
template <typename T>
class sparse_table {
private:
T **_table;
T _n;
T _logn;
inline T _max(const T &a, const T &b) { return (a > b) ? a : b; }

public:
sparse_table(T n, T *a) : _n(n), _logn(lb(n) + 1) {
_table = new T *[_n + 5];
for (int i = 0; i < _n + 5; ++i) _table[i] = new T[_logn + 5];
for (int i = 1; i <= _n; ++i) _table[i][0] = a[i];
for (int j = 1; j <= _logn; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
_table[i][j] =
_max(_table[i][j - 1], _table[i + (1 << (j - 1))][j - 1]);
}
~sparse_table() {
for (int i = 0; i < _n + 5; ++i) delete[] _table[i];
delete[] _table;
}
inline T query(T l, T r) {
T s = lb(r - l + 1);
return _max(_table[l][s], _table[r - (1 << s) + 1][s]);
}
};
本文默认采用 署名-非商业性使用-相同方式共享 4.0 国际 许可证