This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub dnx04/algo
#include "data-structure/fenwick.hpp"
template <typename T> struct fenwick { fenwick(int n) : n(n), f(n + 1) {} // a[u] += val void add(int u, T val) { assert(0 <= u && u < n); ++u; while (u <= n) f[u] += val, u += u & -u; } // return the sum of [0, u) T sum(int u) const { assert(0 <= u && u <= n); T res = 0; while (u) res += f[u], u -= u & -u; return res; } // return the sum of [l, r) T sum(int l, int r) const { assert(0 <= l && l <= r && r <= n); if (l == r) return 0; return sum(r) - sum(l); } void reset() { fill(f.begin(), f.end(), T(0)); } int n; vector<T> f; };
#line 1 "data-structure/fenwick.hpp" template <typename T> struct fenwick { fenwick(int n) : n(n), f(n + 1) {} // a[u] += val void add(int u, T val) { assert(0 <= u && u < n); ++u; while (u <= n) f[u] += val, u += u & -u; } // return the sum of [0, u) T sum(int u) const { assert(0 <= u && u <= n); T res = 0; while (u) res += f[u], u -= u & -u; return res; } // return the sum of [l, r) T sum(int l, int r) const { assert(0 <= l && l <= r && r <= n); if (l == r) return 0; return sum(r) - sum(l); } void reset() { fill(f.begin(), f.end(), T(0)); } int n; vector<T> f; };