This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ruthen71/rcpl
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum" #include <bits/stdc++.h> #include "data_structure/fenwick_tree.hpp" int main() { int N, Q; std::cin >> N >> Q; std::vector<long long> a(N); for (int i = 0; i < N; i++) std::cin >> a[i]; FenwickTree<long long> fen(a); while (Q--) { int t; std::cin >> t; if (t == 0) { int p, x; std::cin >> p >> x; fen.add(p, x); } else { int l, r; std::cin >> l >> r; std::cout << fen.sum(l, r) << '\n'; } } return 0; }
#line 1 "verify/lc_data_structure/lc_point_add_range_sum_fenwick_tree.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum" #include <bits/stdc++.h> #line 2 "data_structure/fenwick_tree.hpp" template <class T> struct FenwickTree { int n; std::vector<T> seg; FenwickTree() : n(0) {} FenwickTree(int n) : n(n), seg(n + 1, 0) {} FenwickTree(std::vector<T>& arr) { n = int(arr.size()); seg.resize(n + 1); for (int i = 0; i < n; i++) add(i, arr[i]); } // A[i] += x void add(int i, const T& x) { assert(0 <= i and i < n); i++; // 1-indexed while (i <= n) { seg[i] += x; i += i & -i; } } // A[0] + ... + A[i - 1] T sum(int i) const { assert(0 <= i and i <= n); T s = T(0); while (i > 0) { s += seg[i]; i -= i & -i; } return s; } // A[a] + ... + A[b - 1] T sum(int a, int b) const { assert(0 <= a and a <= b and b <= n); return sum(b) - sum(a); } // return A[i] T get(int i) const { return sum(i, i + 1); } // A[i] = x void set(int i, const T x) { add(i, x - get(i)); } // output friend std::ostream& operator<<(std::ostream& os, const FenwickTree& fen) { for (int i = 0; i < fen.n; i++) os << fen.get(i) << " \n"[i == fen.n - 1]; return os; } }; #line 6 "verify/lc_data_structure/lc_point_add_range_sum_fenwick_tree.test.cpp" int main() { int N, Q; std::cin >> N >> Q; std::vector<long long> a(N); for (int i = 0; i < N; i++) std::cin >> a[i]; FenwickTree<long long> fen(a); while (Q--) { int t; std::cin >> t; if (t == 0) { int p, x; std::cin >> p >> x; fen.add(p, x); } else { int l, r; std::cin >> l >> r; std::cout << fen.sum(l, r) << '\n'; } } return 0; }