This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub dnx04/algo
#include "data-structure/fenwick2d.hpp"
#include "data-structure/fenwick.hpp" template <class T> struct fenwick2d { int n, m; vector<fenwick<T>> f; fenwick2d(int n, int m) : n(n), m(m), f(n + 1, fenwick<T>(m)) {} void add(int x, int y, T v) { assert(0 <= x && x < n && 0 <= y && y < m); ++x; while (x <= n) f[x].add(y, v), x += x & -x; } // add v to [x1, x2) x [y1, y2) void add(int x1, int y1, int x2, int y2, T v) { add(x1, y1, v); add(x1, y2, -v); add(x2, y1, -v); add(x2, y2, v); } // sum of [0, x) * [0, y) T sum(int x, int y) { T res = 0; while(x) res += f[x].sum(y), x -= x & -x; return res; } // sum of [x1, x2) * [y1, y2) T sum(int x1, int y1, int x2, int y2) { return sum(x2, y2) - sum(x1, y2) - sum(x2, y1) + sum(x1, y1); } };
#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; }; #line 2 "data-structure/fenwick2d.hpp" template <class T> struct fenwick2d { int n, m; vector<fenwick<T>> f; fenwick2d(int n, int m) : n(n), m(m), f(n + 1, fenwick<T>(m)) {} void add(int x, int y, T v) { assert(0 <= x && x < n && 0 <= y && y < m); ++x; while (x <= n) f[x].add(y, v), x += x & -x; } // add v to [x1, x2) x [y1, y2) void add(int x1, int y1, int x2, int y2, T v) { add(x1, y1, v); add(x1, y2, -v); add(x2, y1, -v); add(x2, y2, v); } // sum of [0, x) * [0, y) T sum(int x, int y) { T res = 0; while(x) res += f[x].sum(y), x -= x & -x; return res; } // sum of [x1, x2) * [y1, y2) T sum(int x1, int y1, int x2, int y2) { return sum(x2, y2) - sum(x1, y2) - sum(x2, y1) + sum(x1, y1); } };