This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub dnx04/algo
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum" #include <bits/extc++.h> using namespace std; #include "data-structure/fenwick.hpp" signed main() { ios::sync_with_stdio(false), cin.tie(0); int n, q; cin >> n >> q; fenwick<int64_t> fw(n); for (int i = 0; i < n; ++i) { int x; cin >> x; fw.add(i, x); } while (q--) { int t, l, r; cin >> t >> l >> r; if (t) cout << fw.sum(l, r) << '\n'; else fw.add(l, r); } }
#line 1 "data-structure/test/Point_Add_Range_Sum.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum" #include <bits/extc++.h> using namespace std; #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 8 "data-structure/test/Point_Add_Range_Sum.test.cpp" signed main() { ios::sync_with_stdio(false), cin.tie(0); int n, q; cin >> n >> q; fenwick<int64_t> fw(n); for (int i = 0; i < n; ++i) { int x; cin >> x; fw.add(i, x); } while (q--) { int t, l, r; cin >> t >> l >> r; if (t) cout << fw.sum(l, r) << '\n'; else fw.add(l, r); } }