This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ngthanhtrung23/ACM_Notebook_new
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B" #include <bits/stdc++.h> using namespace std; #include "../Fenwick/Fenwick.h" int main() { ios::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; Fenwick<long long> bit(n); while (q--) { int typ, x, y; cin >> typ >> x >> y; --x; if (typ == 0) bit.update(x, y); else cout << bit.get(x, y) << '\n'; } }
#line 1 "DataStructure/test/aizu_dsl_2_b_fenwick_aizu.test.cpp" #define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B" #include <bits/stdc++.h> using namespace std; #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; }; // }}} #line 7 "DataStructure/test/aizu_dsl_2_b_fenwick_aizu.test.cpp" int main() { ios::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; Fenwick<long long> bit(n); while (q--) { int typ, x, y; cin >> typ >> x >> y; --x; if (typ == 0) bit.update(x, y); else cout << bit.get(x, y) << '\n'; } }