This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ngthanhtrung23/ACM_Notebook_new
// 1D Fenwick {{{ // 0 based index // // Tested: // - https://judge.yosupo.jp/problem/static_range_sum // - https://judge.yosupo.jp/problem/point_add_range_sum template< typename T // need to support operators + - > struct Fenwick { Fenwick(int _n) : n(_n), f(_n + 1) {} // a[u] += val void update(int u, T val) { assert(0 <= u && u < n); ++u; for (; u <= n; u += u & -u) { f[u] += val; } } // return a[0] + .. + a[u-1] T get(int u) const { assert(0 <= u && u <= n); T res = 0; for (; u > 0; u -= u & -u) { res += f[u]; } return res; } // return a[l] + .. + a[r-1] T get(int l, int r) const { assert(0 <= l && l <= r && r <= n); if (l == r) return 0; // empty return get(r) - get(l); } void reset() { std::fill(f.begin(), f.end(), T(0)); } int n; vector<T> f; }; // }}}
#line 1 "DataStructure/Fenwick/Fenwick.h" // 1D Fenwick {{{ // 0 based index // // Tested: // - https://judge.yosupo.jp/problem/static_range_sum // - https://judge.yosupo.jp/problem/point_add_range_sum template< typename T // need to support operators + - > struct Fenwick { Fenwick(int _n) : n(_n), f(_n + 1) {} // a[u] += val void update(int u, T val) { assert(0 <= u && u < n); ++u; for (; u <= n; u += u & -u) { f[u] += val; } } // return a[0] + .. + a[u-1] T get(int u) const { assert(0 <= u && u <= n); T res = 0; for (; u > 0; u -= u & -u) { res += f[u]; } return res; } // return a[l] + .. + a[r-1] T get(int l, int r) const { assert(0 <= l && l <= r && r <= n); if (l == r) return 0; // empty return get(r) - get(l); } void reset() { std::fill(f.begin(), f.end(), T(0)); } int n; vector<T> f; }; // }}}