src/ds/fenwick/d1rr/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../d1/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | template <class T> | ||
| 8 | class fenwick_rr { | ||
| 9 | fenwick<T> a, ai; | ||
| 10 | |||
| 11 | public: | ||
| 12 | //! [1, sz) | ||
| 13 | 22 | CEXPE fenwick_rr(u32 sz) NE : a(sz), ai(sz) {} | |
| 14 | |||
| 15 | //! [pos, sz), pos > 0 | ||
| 16 | 852970 | CEXP void add(u32 pos, cT_(T) x) NE { a.add(pos, x), ai.add(pos, x * (pos - 1)); } | |
| 17 | //! [l, r], l > 0 | ||
| 18 | 426485 | CEXP void add(u32 l, u32 r, cT_(T) x) NE { add(l, x), add(r + 1, -x); } | |
| 19 | //! [1, pos] | ||
| 20 | 853306 | CEXP T sum(u32 pos) NE { return pos * a.sum(pos) - ai.sum(pos); } | |
| 21 | //! [l, r] | ||
| 22 | 426653 | CEXP T sum(u32 l, u32 r) NE { return sum(r) - sum(l - 1); } | |
| 23 | }; | ||
| 24 | |||
| 25 | } // namespace tifa_libs | ||
| 26 |