src/ds/fenwick/d1/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../../bit/lowbit/lib.hpp" | ||
| 4 | #include "../../../util/alias/others/lib.hpp" | ||
| 5 | |||
| 6 | namespace tifa_libs { | ||
| 7 | |||
| 8 | template <class T> | ||
| 9 | class fenwick { | ||
| 10 | vec<T> a; | ||
| 11 | |||
| 12 | public: | ||
| 13 | //! [1, sz) | ||
| 14 |
3/6tifa_libs::fenwick<long>::fenwick(unsigned int):
✗ Branch 1 not taken.
✓ Branch 2 taken 16 times.
tifa_libs::fenwick<unsigned int>::fenwick(unsigned int):
✗ Branch 1 not taken.
✓ Branch 2 taken 60 times.
tifa_libs::fenwick<unsigned long>::fenwick(unsigned int):
✗ Branch 1 not taken.
✓ Branch 2 taken 106 times.
|
546 | CEXPE fenwick(u32 sz) NE : a(sz) { assert(sz > 1); } |
| 15 | //! [1, sz) | ||
| 16 | 32 | CEXP fenwick(spn<T> data) NE : fenwick((u32)data.size()) { | |
| 17 | 32 | cu32 sz = (u32)data.size(); | |
| 18 |
2/2✓ Branch 0 taken 8224977 times.
✓ Branch 1 taken 32 times.
|
8225009 | flt_ (u32, i, 1, sz) { |
| 19 | 8224977 | a[i] += data[i]; | |
| 20 |
2/2✓ Branch 1 taken 8224804 times.
✓ Branch 2 taken 173 times.
|
8224977 | if (cu32 j = i + lowbit(i); j < sz) a[j] += a[i]; |
| 21 | } | ||
| 22 | 32 | } | |
| 23 | |||
| 24 | //! [pos, sz), pos > 0 | ||
| 25 | 59288414 | CEXP void add(u32 pos, cT_(T) x) NE { | |
| 26 |
3/6tifa_libs::fenwick<long>::add(unsigned int, long):
✗ Branch 0 not taken.
✓ Branch 1 taken 53449174 times.
tifa_libs::fenwick<unsigned int>::add(unsigned int, unsigned int):
✗ Branch 0 not taken.
✓ Branch 1 taken 412778 times.
tifa_libs::fenwick<unsigned long>::add(unsigned int, unsigned long):
✗ Branch 0 not taken.
✓ Branch 1 taken 5426462 times.
|
59288414 | if (!pos) return; |
| 27 |
6/6tifa_libs::fenwick<long>::add(unsigned int, long):
✓ Branch 3 taken 833881802 times.
✓ Branch 4 taken 53449174 times.
tifa_libs::fenwick<unsigned int>::add(unsigned int, unsigned int):
✓ Branch 3 taken 3573301 times.
✓ Branch 4 taken 412778 times.
tifa_libs::fenwick<unsigned long>::add(unsigned int, unsigned long):
✓ Branch 3 taken 48681365 times.
✓ Branch 4 taken 5426462 times.
|
945424882 | for (; pos < a.size(); pos += lowbit(pos)) a[pos] += x; |
| 28 | } | ||
| 29 | //! [l, r], l > 0 | ||
| 30 | CEXP void add(u32 l, u32 r, cT_(T) x) NE { add(l, x), add(r + 1, -x); } | ||
| 31 | //! [1, pos] | ||
| 32 | 17552857 | CEXP T sum(u32 pos) NE { | |
| 33 | 17552857 | T ret = 0; | |
| 34 |
6/6tifa_libs::fenwick<long>::sum(unsigned int):
✓ Branch 4 taken 17746803 times.
✓ Branch 5 taken 1917488 times.
tifa_libs::fenwick<unsigned int>::sum(unsigned int):
✓ Branch 4 taken 4467066 times.
✓ Branch 5 taken 623008 times.
tifa_libs::fenwick<unsigned long>::sum(unsigned int):
✓ Branch 4 taken 130657066 times.
✓ Branch 5 taken 15012361 times.
|
170423792 | for (pos = min(pos, (u32)a.size() - 1); pos; pos -= lowbit(pos)) ret += a[pos]; |
| 35 | 17552857 | return ret; | |
| 36 | } | ||
| 37 | //! [l, r] | ||
| 38 | 311407 | CEXP T sum(u32 l, u32 r) NE { return sum(r) - sum(l - 1); } | |
| 39 | //! for weighted fenwick | ||
| 40 | CEXP T kth_max(u32 k) NE { | ||
| 41 | cu32 n = std::bit_ceil(a.size()); | ||
| 42 | u32 now = 0; | ||
| 43 | T s{}; | ||
| 44 | while (n) | ||
| 45 | if (cu32 to = now | n; to >= a.size()) continue; | ||
| 46 | else if (T x = s + a[to]; x < k) now = to, s = x; | ||
| 47 | return now + 1; | ||
| 48 | } | ||
| 49 | }; | ||
| 50 | |||
| 51 | } // namespace tifa_libs | ||
| 52 |