This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub SSRS-cp/cp_library
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum" #include <bits/stdc++.h> using namespace std; #include "../../../data_structure/sequence/binary_indexed_tree.hpp" int main(){ int N, Q; cin >> N >> Q; vector<long long> a(N); for (int i = 0; i < N; i++){ cin >> a[i]; } binary_indexed_tree<long long> BIT(a, plus<long long>(), 0); for (int i = 0; i < Q; i++){ int t; cin >> t; if (t == 0){ int p, x; cin >> p >> x; BIT.add(p, x); } if (t == 1){ int l, r; cin >> l >> r; cout << BIT.sum(r) - BIT.sum(l) << endl; } } }
#line 1 "test/library_checker/data_structure/point_add_range_sum.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum" #include <bits/stdc++.h> using namespace std; #line 2 "data_structure/sequence/binary_indexed_tree.hpp" /** * @brief Binary Indexed Tree */ template <typename T> struct binary_indexed_tree{ int N; vector<T> BIT; function<T(T, T)> f; T E; binary_indexed_tree(){ } binary_indexed_tree(int N, function<T(T, T)> f, T E): N(N), BIT(N + 1, E), f(f), E(E){ } binary_indexed_tree(vector<T> &A, function<T(T, T)> f, T E): N(A.size()), BIT(N + 1), f(f), E(E){ for (int i = 0; i < N; i++){ BIT[i + 1] = A[i]; } for (int i = 1; i < N; i++){ if (i + (i & -i) <= N){ BIT[i + (i & -i)] = f(BIT[i + (i & -i)], BIT[i]); } } } void add(int i, T x){ i++; while (i <= N){ BIT[i] = f(BIT[i], x); i += i & -i; } } T sum(int i){ T ans = E; while (i > 0){ ans = f(ans, BIT[i]); i -= i & -i; } return ans; } }; #line 5 "test/library_checker/data_structure/point_add_range_sum.test.cpp" int main(){ int N, Q; cin >> N >> Q; vector<long long> a(N); for (int i = 0; i < N; i++){ cin >> a[i]; } binary_indexed_tree<long long> BIT(a, plus<long long>(), 0); for (int i = 0; i < Q; i++){ int t; cin >> t; if (t == 0){ int p, x; cin >> p >> x; BIT.add(p, x); } if (t == 1){ int l, r; cin >> l >> r; cout << BIT.sum(r) - BIT.sum(l) << endl; } } }