diff options
Diffstat (limited to 'datastructures')
| -rw-r--r-- | datastructures/segmentTree.cpp | 7 | ||||
| -rw-r--r-- | datastructures/test/segmentTree.awk | 74 | ||||
| -rw-r--r-- | datastructures/test/segmentTree.cpp | 80 | ||||
| -rw-r--r-- | datastructures/test/segmentTree2.cpp | 26 |
4 files changed, 153 insertions, 34 deletions
diff --git a/datastructures/segmentTree.cpp b/datastructures/segmentTree.cpp index 2cbf466..4f75d03 100644 --- a/datastructures/segmentTree.cpp +++ b/datastructures/segmentTree.cpp @@ -4,14 +4,15 @@ struct SegTree { vector<T> tree; static constexpr T E = 0; // Neutral element for combine - SegTree(vector<T>& a) : n(ssize(a)), tree(2 * n) { - //SegTree(int size, T val = E) : n(size), tree(2 * n, val) { + SegTree(vector<T>& a) : n(ssize(a)), tree(2 * n, E) { ranges::copy(a, tree.begin() + n); + //SegTree(int size, T val = E) : n(size), tree(2 * n, E) { + // fill(tree.begin() + n, tree.end(), val); for (int i = n - 1; i > 0; i--) { // remove for range update tree[i] = comb(tree[2 * i], tree[2 * i + 1]); }} - ll comb(T a, T b) {return a + b;} // modify this + neutral + ll comb(T a, T b) { return a + b; } // modify this + neutral void update(int i, T val) { tree[i += n] = val; // apply update code diff --git a/datastructures/test/segmentTree.awk b/datastructures/test/segmentTree.awk new file mode 100644 index 0000000..e863d4e --- /dev/null +++ b/datastructures/test/segmentTree.awk @@ -0,0 +1,74 @@ + +/Neutral element for combine/ { + print "#ifndef SEGTREE_MUL" + print "# ifndef SEGTREE_FIRST_NEG" + print + print "# else" + tmp = $0 + sub(/0/, "numeric_limits<ll>::max()", tmp) + print tmp + print "# endif" + print "#else" + sub(/0/, "1") + print + print "#endif" + next +} + +/modify this \+ neutral/ { + print "#ifndef SEGTREE_MUL" + print "# ifndef SEGTREE_FIRST_NEG" + print + print "# else" + tmp = $0 + sub(/a \+ b/, "a < 0 ? a : min(a, b)", tmp) + print tmp + print "# endif" + print "#else" + sub(/a \+ b/, "a*b % MOD") + print + print "#endif" + next +} + +/SegTree\(vector<T>& a\)/ { + print "#ifndef SEGTREE_INIT_DEFAULT" + print + getline + print + print "#else" + getline + sub(/\/\//, "") + print + getline + sub(/\/\//, "") + print + print "#endif" + next +} + +/remove for range update/ { + print "#ifndef SEGTREE_RANGE_UPDATE" + print + getline + print + getline + print "\t\t}" + print "#endif" + print "\t}" + next +} + +/void update/ { + print "#ifndef SEGTREE_RANGE_UPDATE" +} + +/OR: range update/ { + print "#else" +} + +/^\};$/ { + print "#endif" +} + +{ print } diff --git a/datastructures/test/segmentTree.cpp b/datastructures/test/segmentTree.cpp index 79c16e6..44d99b6 100644 --- a/datastructures/test/segmentTree.cpp +++ b/datastructures/test/segmentTree.cpp @@ -1,25 +1,74 @@ +#ifdef SEGTREE_MUL +constexpr ll MOD = 1'000'000'007; +#endif + #include "segmentTree.tmp.cpp" void test(int n) { +#ifndef SEGTREE_INIT_DEFAULT vector<ll> a(n); for (ll &x: a) x = util::randint(); SegTree seg(a); +#else + ll init = util::randint(); +# ifdef SEGTREE_FIRST_NEG + init = abs(init); +# endif + vector<ll> a(n, init); + SegTree seg(n, init); +#endif for (int i = 0; i < 5*n; i++) { { +#ifndef SEGTREE_RANGE_UPDATE int j = util::randint(n); ll v = util::randint(); a[j] = v; seg.update(j, v); +#else + int l = util::randint(n+1); + int r = util::randint(n+1); + if (l > r) swap(l, r); + ll v = util::randint(); + for (int j = l; j < r; j++) { +# ifndef SEGTREE_MUL + a[j] += v; +# else + a[j] = a[j]*v % MOD; +# endif + } + seg.modify(l, r, v); +#endif } { +#ifndef SEGTREE_RANGE_UPDATE int l = util::randint(n+1); int r = util::randint(n+1); if (l > r) swap(l, r); - assert( - seg.query(l, r) - == - accumulate(a.begin() + l, a.begin() + r, 0ll) - ); +# ifndef SEGTREE_MUL +# ifndef SEGTREE_FIRST_NEG + ll comp = 0; +# else + ll comp = numeric_limits<ll>::max(); +# endif +# else + ll comp = 1; +# endif + for (int j = l; j < r; j++) { +# ifndef SEGTREE_MUL +# ifndef SEGTREE_FIRST_NEG + comp += a[j]; +# else + if (comp >= 0 && comp > a[j]) comp = a[j]; +# endif +# else + comp = comp * a[j] % MOD; +# endif + } + assert(seg.query(l, r) == comp); +#else + int j = util::randint(n); + assert(seg.query(j) == a[j]); +#endif } } } @@ -27,4 +76,25 @@ void test(int n) { int main() { test(1000); test(1); + { +#ifndef SEGTREE_INIT_DEFAULT + vector<ll> a; + SegTree seg(a); +#else + SegTree seg(0); +#endif +#ifndef SEGTREE_RANGE_UPDATE +# ifndef SEGTREE_MUL +# ifndef SEGTREE_FIRST_NEG + assert(seg.query(0, 0) == 0); +# else + assert(seg.query(0, 0) == numeric_limits<ll>::max()); +# endif +# else + assert(seg.query(0, 0) == 1); +# endif +#else + seg.modify(0, 0, util::randint()); +#endif + } } diff --git a/datastructures/test/segmentTree2.cpp b/datastructures/test/segmentTree2.cpp deleted file mode 100644 index f403a1d..0000000 --- a/datastructures/test/segmentTree2.cpp +++ /dev/null @@ -1,26 +0,0 @@ -#include "segmentTree2.tmp.cpp" - -void test(int n) { - vector<ll> a(n); - for (ll &x: a) x = util::randint(); - SegTree seg(a); - for (int i = 0; i < 5*n; i++) { - { - int l = util::randint(n+1); - int r = util::randint(n+1); - if (l > r) swap(l, r); - ll v = util::randint(); - for (int i = l; i < r; i++) a[i] += v; - seg.modify(l, r, v); - } - { - int j = util::randint(n); - assert(seg.query(j) == a[j]); - } - } -} - -int main() { - test(1000); - test(1); -} |