diff options
| -rw-r--r-- | Makefile | 7 | ||||
| -rw-r--r-- | datastructures/sparseTable.cpp | 6 | ||||
| -rw-r--r-- | datastructures/sparseTableDisjoint.cpp | 12 | ||||
| -rw-r--r-- | datastructures/test/sparseTable.cpp | 24 | ||||
| -rw-r--r-- | datastructures/test/sparseTableDisjoint.cpp | 24 | ||||
| -rw-r--r-- | graph/LCA_sparse.cpp | 2 |
6 files changed, 65 insertions, 10 deletions
@@ -3,6 +3,8 @@ TESTS = \ datastructures/test/fenwickTree2.test \ datastructures/test/monotonicConvexHull.test \ datastructures/test/persistent.test \ + datastructures/test/sparseTable.test \ + datastructures/test/sparseTableDisjoint.test \ graph/test/binary_lifting.test \ graph/test/LCA_sparse.test \ math/test/binomial0.test @@ -47,6 +49,11 @@ datastructures/test/monotonicConvexHull.test: \ datastructures/monotonicConvexHull.cpp datastructures/test/persistent.test: datastructures/test/persistent.cpp \ datastructures/persistent.cpp +datastructures/test/sparseTable.test: datastructures/test/sparseTable.cpp \ + datastructures/sparseTable.cpp +datastructures/test/sparseTableDisjoint.test: \ + datastructures/test/sparseTableDisjoint.cpp \ + datastructures/sparseTableDisjoint.cpp graph/test/binary_lifting.test: graph/test/binary_lifting.cpp \ graph/binary_lifting.cpp graph/test/util.cpp graph/test/LCA_sparse.test: graph/test/LCA_sparse.cpp \ diff --git a/datastructures/sparseTable.cpp b/datastructures/sparseTable.cpp index 63cce48..64a892a 100644 --- a/datastructures/sparseTable.cpp +++ b/datastructures/sparseTable.cpp @@ -6,9 +6,9 @@ struct SparseTable { return a[lidx] <= a[ridx] ? lidx : ridx; } - void init(vector<ll> *vec) { - int n = sz(*vec); - a = vec->data(); + void init(vector<ll> &vec) { + int n = sz(vec); + a = vec.data(); st.assign(__lg(n) + 1, vector<int>(n)); iota(all(st[0]), 0); for (int j = 0; (2 << j) <= n; j++) { diff --git a/datastructures/sparseTableDisjoint.cpp b/datastructures/sparseTableDisjoint.cpp index 31e9025..dc5297a 100644 --- a/datastructures/sparseTableDisjoint.cpp +++ b/datastructures/sparseTableDisjoint.cpp @@ -1,5 +1,5 @@ struct DisjointST { - static constexpr ll neutral = 0 + static constexpr ll neutral = 0; vector<vector<ll>> dst; ll* a; @@ -7,16 +7,16 @@ struct DisjointST { return x + y; } - void init(vector<ll> *vec) { - int n = sz(*vec); - a = vec->data(); + void init(vector<ll> &vec) { + int n = sz(vec); + a = vec.data(); dst.assign(__lg(n) + 1, vector<ll>(n + 1, neutral)); for (int h = 0, l = 1; l <= n; h++, l *= 2) { for (int c = l; c < n + l; c += 2 * l) { for (int i = c; i < min(n, c + l); i++) - dst[h][i + 1] = combine(dst[h][i], vec->at(i)); + dst[h][i + 1] = combine(dst[h][i], vec[i]); for (int i = min(n, c); i > c - l; i--) - dst[h][i - 1] = combine(vec->at(i - 1), dst[h][i]); + dst[h][i - 1] = combine(vec[i - 1], dst[h][i]); }}} ll query(int l, int r) { diff --git a/datastructures/test/sparseTable.cpp b/datastructures/test/sparseTable.cpp new file mode 100644 index 0000000..ed4d61f --- /dev/null +++ b/datastructures/test/sparseTable.cpp @@ -0,0 +1,24 @@ +#include "../sparseTable.cpp" + +void test(int n) { + vector<ll> values(n); + for (ll &x: values) x = util::randint(); + SparseTable st; + st.init(values); + for (int i = 0; i < n; i++) { + int l = util::randint(n); + int r = util::randint(n); + if (l > r) swap(l, r); + r++; + assert( + values[st.queryIdempotent(l, r)] + == + *min_element(values.begin()+l, values.begin()+r) + ); + } +} + +int main() { + test(1000); + test(1); +} diff --git a/datastructures/test/sparseTableDisjoint.cpp b/datastructures/test/sparseTableDisjoint.cpp new file mode 100644 index 0000000..43c6d6e --- /dev/null +++ b/datastructures/test/sparseTableDisjoint.cpp @@ -0,0 +1,24 @@ +#include "../sparseTableDisjoint.cpp" + +void test(int n) { + vector<ll> values(n); + for (ll &x: values) x = util::randint(); + DisjointST st; + st.init(values); + for (int i = 0; i < n; i++) { + int l = util::randint(n); + int r = util::randint(n); + if (l > r) swap(l, r); + r++; + assert( + st.query(l, r) + == + accumulate(values.begin()+l, values.begin()+r, 0ll) + ); + } +} + +int main() { + test(1000); + test(1); +} diff --git a/graph/LCA_sparse.cpp b/graph/LCA_sparse.cpp index 0f2fe22..06b294f 100644 --- a/graph/LCA_sparse.cpp +++ b/graph/LCA_sparse.cpp @@ -10,7 +10,7 @@ struct LCA { first.assign(sz(adj), 2 * sz(adj)); idx = 0; dfs(adj, root); - st.init(&depth); + st.init(depth); } void dfs(vector<vector<int>>& adj, int v, ll d=0) { |