Skip to content

Commit d054f73

Browse files
zimphazimpha
committed
add RangeMinimumQuery
1 parent 06f33b1 commit d054f73

23 files changed

+552
-41
lines changed

‎RangeMinimumQuery/DirectRMQ.h

Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
#include <memory>
2+
#include <cstring>
3+
#include <vector>
4+
#include <functional>
5+
6+
template <class T, class Compare = std::less<T>>
7+
class DirectRMQ {
8+
public:
9+
void build(const std::vector<T> &a) {
10+
build(a.data(), a.size());
11+
}
12+
13+
void build(const T *a, int n) {
14+
block_size = 32 - __builtin_clz(n);
15+
blocks = (n + block_size - 1) / block_size;
16+
buildSparseTable(a, n);
17+
buildInnerBlocks(a, n);
18+
}
19+
20+
int query(const T *a, int l, int r) { // [l, r]
21+
const auto &table = sparse_table;
22+
int x = l / block_size + 1, y = r / block_size - 1, z, mask;
23+
int ret = l;
24+
if (x <= y) {
25+
z = block_size - lookup[y - x + 1] - 1;
26+
ret = leftMinIndex(a, table[x + z * blocks], table[y - (1 << z) + 1 + z * blocks]);
27+
}
28+
z = x * block_size - 1 < r ? x * block_size - 1 : r;
29+
mask = ~(((1 << (l - (x - 1) * block_size)) - 1) << (x * block_size - l));
30+
ret = leftMinIndex(a, (x - 1) * block_size + lookup[blocks_type[z] & mask], ret);
31+
z = r, l = l > (y + 1) * block_size ? l : (y + 1) * block_size;
32+
mask = ~(((1 << (l - (y + 1) * block_size)) - 1) << ((y + 2) * block_size -l));
33+
ret = leftMinIndex(a, ret, (y + 1) * block_size + lookup[blocks_type[z] & mask]);
34+
return ret;
35+
}
36+
37+
private:
38+
int minIndex(const T *a, int x, int y) {
39+
return compare(a[x], a[y]) || (a[x] == a[y] && x < y) ? x : y;
40+
}
41+
42+
int leftMinIndex(const T *a, int x, int y) {
43+
return compare(a[y], a[x]) ? y : x;
44+
}
45+
46+
void buildSparseTable(const T *a, int n) {
47+
int height = 0;
48+
while ((1 << height) < blocks) ++height;
49+
sparse_table.resize(blocks * height);
50+
int *u = &sparse_table[0];
51+
for (int i = 0, idx = 0; i < n; i += block_size, ++idx) {
52+
u[idx] = i;
53+
for (int j = i + 1; j < n && j < i + block_size; ++j) {
54+
u[idx] = leftMinIndex(a, u[idx], j);
55+
}
56+
}
57+
for (int t = 1; t * 2 < blocks; t *= 2) {
58+
memcpy(u + blocks, u, sizeof(int) * blocks);
59+
u += blocks;
60+
for (int i = 0; i < blocks - t; ++i) {
61+
u[i] = leftMinIndex(a, u[i], u[i + t]);
62+
}
63+
}
64+
}
65+
66+
void buildInnerBlocks(const T *a, int n) {
67+
lookup.assign(1 << block_size, 0);
68+
blocks_type.assign(n, 0);
69+
std::vector<int> stack(block_size);
70+
for (int i = 0; i < blocks; ++i) {
71+
int l = i * block_size;
72+
int r = std::min(n, l + block_size);
73+
for (int j = l, top = 0; j < r; ++j) {
74+
while (top && compare(a[j], a[stack[top - 1]])) --top;
75+
blocks_type[j] = 1 << (l + block_size - j - 1);
76+
if (top) {
77+
blocks_type[j] |= blocks_type[stack[top - 1]];
78+
}
79+
stack[top++] = j;
80+
}
81+
}
82+
for (int i = 1, res = block_size - 1; i < (1 << block_size); ++i) {
83+
if ((1 << (block_size - res)) <= i) --res;
84+
lookup[i] = res;
85+
}
86+
}
87+
88+
std::vector<int> lookup;
89+
std::vector<int> blocks_type;
90+
std::vector<int> sparse_table;
91+
int block_size, blocks;
92+
Compare compare;
93+
};

‎RangeMinimumQuery/DynamicRMQ.h

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
#include <vector>
2+
#include <algorithm>
3+
4+
template <class T, T combine(T, T)>
5+
class DynamicRMQ {
6+
public:
7+
void build(const std::vector<T> &data) {
8+
build(&data[0], data.size());
9+
}
10+
void build(const T *data, int n) {
11+
u.resize(n * 2);
12+
for (int i = 0; i < n; ++i) {
13+
u[i + n] = data[i];
14+
}
15+
for (int i = n - 1; i > 0; --i) {
16+
u[i] = combine(u[i << 1], u[i << 1 | 1]);
17+
}
18+
}
19+
void modify(int p, const T& v) {
20+
for (u[p += u.size() / 2] = v; p > 1; p >>= 1) {
21+
u[p >> 1] = combine(u[p], u[p ^ 1]);
22+
}
23+
}
24+
T query(int l, int r, T res = T()) {// [l, r)
25+
const int n = u.size() >> 1;
26+
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
27+
if (l & 1) res = combine(res, u[l++]);
28+
if (r & 1) res = combine(res, u[--r]);
29+
}
30+
return res;
31+
}
32+
private:
33+
std::vector<T> u;
34+
};

‎RangeMinimumQuery/OfflineRMQ.h

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
#include <vector>
2+
#include <functional>
3+
4+
template <class T, class Compare = std::less<T>>
5+
class OfflineRMQ {
6+
public:
7+
std::vector<T> solve(const std::vector<T> &a, const std::vector<int> &L, const std::vector<int> &R) {
8+
const int n = a.size(), q = L.size();
9+
std::vector<int> prev(q), head(n, -1), parent(n, -1);
10+
std::function<int(int)> root = [&](int x) {
11+
return parent[x] == -1 ? x : parent[x] = root(parent[x]);
12+
};
13+
14+
for (int i = 0; i < q; ++i) {
15+
prev[i] = head[R[i]];
16+
head[R[i]] = i;
17+
}
18+
std::vector<int> stack(n);
19+
std::vector<T> result(q);
20+
for (int i = 0, top = 0; i < n; ++i) {
21+
while (top && compare(a[i], a[stack[top - 1]])) {
22+
parent[stack[--top]] = i;
23+
}
24+
stack[top++] = i;
25+
for (int it = head[i]; ~it; it = prev[it]) {
26+
result[it] = a[root(L[it])];
27+
}
28+
}
29+
return result;
30+
}
31+
private:
32+
Compare compare;
33+
};

‎data-structure/RangeMinimumQuery.cc renamed to ‎RangeMinimumQuery/SchieberVishkinRMQ.h

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -87,7 +87,7 @@ class SchieberVishkinRMQ {
8787
private:
8888
using uint = unsigned int;
8989
static uint lowbit(uint x) {
90-
return x & ~x + 1; // x & (-x) or x & (x ^ (x - 1))
90+
return x & (~x + 1); // x & (-x) or x & (x ^ (x - 1))
9191
}
9292
static uint highbit(uint x) {
9393
return 1u << (31 - __builtin_clz(x));

‎RangeMinimumQuery/main.cc

Lines changed: 151 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,151 @@
1+
#include "DirectRMQ.h"
2+
#include "DynamicRMQ.h"
3+
#include "OfflineRMQ.h"
4+
#include "SchieberVishkinRMQ.h"
5+
6+
inline int min(int a, int b) {
7+
return std::min(a, b);
8+
}
9+
10+
int main() {
11+
clock_t st, ed;
12+
srand(2333);
13+
const int n = 10000000, q = 10000000;
14+
std::vector<int> a(n), l(q), r(q);
15+
for (int i = 0; i < n; ++i) a[i] = rand();
16+
printf("rmq benchmark for n = %d, q = %d\n", n, q);
17+
18+
st = clock();
19+
DirectRMQ<int> di_rmq;
20+
di_rmq.build(a);
21+
ed = clock();
22+
printf("build time for DirectRMQ: %.3f sec\n", double(ed - st) / CLOCKS_PER_SEC);
23+
24+
st = clock();
25+
SchieberVishkinRMQ<int> sv_rmq;
26+
sv_rmq.build(a);
27+
ed = clock();
28+
printf("build time for SchieberVishkinRMQ: %.3f sec\n", double(ed - st) / CLOCKS_PER_SEC);
29+
30+
st = clock();
31+
DynamicRMQ<int, min> dy_rmq;
32+
dy_rmq.build(a);
33+
ed = clock();
34+
printf("build time for DynamicRMQ: %.3f sec\n", double(ed - st) / CLOCKS_PER_SEC);
35+
36+
OfflineRMQ<int> of_rmq;
37+
38+
std::vector<int> di_ans(q), sv_ans(q), dy_ans(q), of_ans;
39+
40+
// small interval
41+
puts("test small intervals:");
42+
for (int i = 0; i < q; ++i) {
43+
l[i] = rand() % n;
44+
r[i] = std::min(n - 1, l[i] + rand() % 40);
45+
}
46+
st = clock();
47+
for (int i = 0; i < q; ++i) {
48+
di_ans[i] = a[di_rmq.query(a.data(), l[i], r[i])];
49+
}
50+
ed = clock();
51+
printf(" - query time for DirectRMQ: %.3f sec\n", double(ed - st) / CLOCKS_PER_SEC);
52+
53+
st = clock();
54+
for (int i = 0; i < q; ++i) {
55+
sv_ans[i] = a[sv_rmq.query(l[i], r[i])];
56+
}
57+
ed = clock();
58+
printf(" - query time for SchieberVishkinRMQ: %.3f sec\n", double(ed - st) / CLOCKS_PER_SEC);
59+
60+
st = clock();
61+
for (int i = 0; i < q; ++i) {
62+
dy_ans[i] = dy_rmq.query(l[i], r[i] + 1, INT32_MAX);
63+
}
64+
ed = clock();
65+
printf(" - query time for DynamicRMQ: %.3f sec\n", double(ed - st) / CLOCKS_PER_SEC);
66+
67+
st = clock();
68+
of_ans = of_rmq.solve(a, l, r);
69+
ed = clock();
70+
printf(" - query time for OfflineRMQ: %.3f sec\n", double(ed - st) / CLOCKS_PER_SEC);
71+
72+
for (int i = 0; i < q; ++i) {
73+
assert(di_ans[i] == sv_ans[i] && sv_ans[i] == dy_ans[i] && dy_ans[i] == of_ans[i]);
74+
}
75+
76+
// random interval
77+
puts("test random queries:");
78+
for (int i = 0; i < q; ++i) {
79+
l[i] = rand() % n;
80+
r[i] = rand() % n;
81+
if (l[i] > r[i]) std::swap(l[i], r[i]);
82+
}
83+
84+
st = clock();
85+
for (int i = 0; i < q; ++i) {
86+
di_ans[i] = a[di_rmq.query(a.data(), l[i], r[i])];
87+
}
88+
ed = clock();
89+
printf(" - query time for DirectRMQ: %.3f sec\n", double(ed - st) / CLOCKS_PER_SEC);
90+
91+
st = clock();
92+
for (int i = 0; i < q; ++i) {
93+
sv_ans[i] = a[sv_rmq.query(l[i], r[i])];
94+
}
95+
ed = clock();
96+
printf(" - query time for SchieberVishkinRMQ: %.3f sec\n", double(ed - st) / CLOCKS_PER_SEC);
97+
98+
st = clock();
99+
for (int i = 0; i < q; ++i) {
100+
dy_ans[i] = dy_rmq.query(l[i], r[i] + 1, INT32_MAX);
101+
}
102+
ed = clock();
103+
printf(" - query time for DynamicRMQ: %.3f sec\n", double(ed - st) / CLOCKS_PER_SEC);
104+
105+
st = clock();
106+
of_ans = of_rmq.solve(a, l, r);
107+
ed = clock();
108+
printf(" - query time for OfflineRMQ: %.3f sec\n", double(ed - st) / CLOCKS_PER_SEC);
109+
110+
for (int i = 0; i < q; ++i) {
111+
assert(di_ans[i] == sv_ans[i] && sv_ans[i] == dy_ans[i] && dy_ans[i] == of_ans[i]);
112+
}
113+
114+
// large interval
115+
puts("test large intervals:");
116+
for (int i = 0; i < q; ++i) {
117+
l[i] = rand() % 1000;
118+
r[i] = n - 1 - rand() % 1000;
119+
if (l[i] > r[i]) std::swap(l[i], r[i]);
120+
}
121+
for (int i = 0; i < q; ++i) {
122+
l[i] = rand() % n;
123+
r[i] = std::min(n - 1, l[i] + rand() % 40);
124+
}
125+
st = clock();
126+
for (int i = 0; i < q; ++i) {
127+
di_ans[i] = a[di_rmq.query(a.data(), l[i], r[i])];
128+
}
129+
ed = clock();
130+
printf(" - query time for DirectRMQ: %.3f sec\n", double(ed - st) / CLOCKS_PER_SEC);
131+
132+
st = clock();
133+
for (int i = 0; i < q; ++i) {
134+
sv_ans[i] = a[sv_rmq.query(l[i], r[i])];
135+
}
136+
ed = clock();
137+
printf(" - query time for SchieberVishkinRMQ: %.3f sec\n", double(ed - st) / CLOCKS_PER_SEC);
138+
139+
st = clock();
140+
for (int i = 0; i < q; ++i) {
141+
dy_ans[i] = dy_rmq.query(l[i], r[i] + 1, INT32_MAX);
142+
}
143+
ed = clock();
144+
printf(" - query time for DynamicRMQ: %.3f sec\n", double(ed - st) / CLOCKS_PER_SEC);
145+
146+
st = clock();
147+
of_ans = of_rmq.solve(a, l, r);
148+
ed = clock();
149+
printf(" - query time for OfflineRMQ: %.3f sec\n", double(ed - st) / CLOCKS_PER_SEC);
150+
return 0;
151+
}

‎string-utility/Aho-Corasick.cc renamed to ‎StringUtility/Aho-Corasick.cc

File renamed without changes.

‎string-utility/SuffixArray.cc renamed to ‎StringUtility/SuffixArray.cc

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
#include "../data-structure/RangeMinimumQuery.cc"
1+
#include "../RangeMinimumQuery/SchieberVishkinRMQ.cc"
22
#include <cstring>
33
#include <vector>
44
#include <algorithm>

‎string-utility/bit-lcs.cc renamed to ‎StringUtility/bit-lcs.cc

File renamed without changes.

‎string-utility/cyclic-longest-common-string.cc renamed to ‎StringUtility/cyclic-longest-common-string.cc

File renamed without changes.

‎string-utility/eertree.cc renamed to ‎StringUtility/eertree.cc

File renamed without changes.

‎string-utility/ext-kmp.cc renamed to ‎StringUtility/ext-kmp.cc

File renamed without changes.

‎string-utility/hashing.cc renamed to ‎StringUtility/hashing.cc

File renamed without changes.

‎string-utility/kmp.cc renamed to ‎StringUtility/kmp.cc

File renamed without changes.

‎string-utility/lempel-ziv-factorization.cc renamed to ‎StringUtility/lempel-ziv-factorization.cc

File renamed without changes.

‎string-utility/lexicographically-minimal-string-rotation.cc renamed to ‎StringUtility/lexicographically-minimal-string-rotation.cc

File renamed without changes.

‎string-utility/lyndon-word-factorization.cc renamed to ‎StringUtility/lyndon-word-factorization.cc

File renamed without changes.

‎string-utility/manacher.cc renamed to ‎StringUtility/manacher.cc

File renamed without changes.

‎string-utility/palindomic-factorization.cc renamed to ‎StringUtility/palindomic-factorization.cc

File renamed without changes.

‎string-utility/subsequence-automaton.cc renamed to ‎StringUtility/subsequence-automaton.cc

File renamed without changes.

‎string-utility/suffix-automaton.cc renamed to ‎StringUtility/suffix-automaton.cc

File renamed without changes.

‎string-utility/suffix-tree.cc renamed to ‎StringUtility/suffix-tree.cc

File renamed without changes.

0 commit comments

Comments
 (0)