Some Code Template Just for Fun.
View the Project on GitHub Yuri3-xr/CP-library
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum" #include "../DataStructure/SegmentTree.hpp" #include "../Template/Template.hpp" struct Info { i64 x = 0; }; Info operator+(const Info& a, const Info& b) { return {a.x + b.x}; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, q; std::cin >> n >> q; std::vector<Info> a(n); for (auto&& it : a) std::cin >> it.x; SegmentTree<Info> st(a); while (q--) { int op; std::cin >> op; if (op == 0) { int p, x; std::cin >> p >> x; st.update(p, {st[p].x + x}); } else { int l, r; std::cin >> l >> r; std::cout << st.query(l, r).x << '\n'; } } return 0; }
#line 1 "Verify/PointAddRangeSum.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum" #line 2 "Template/Template.hpp" #include <bits/stdc++.h> using i64 = std::int64_t; #line 3 "DataStructure/SegmentTree.hpp" template <typename Info> struct SegmentTree { int N; int size; std::vector<Info> seg; SegmentTree(int _N) { init(_N); } //[0,v.size) SegmentTree(const std::vector<Info> &v) { init(v.size()); for (int i = 0; i < (int)v.size(); i++) { seg[i + size] = v[i]; } build(); } void init(int _N) { N = _N; size = 1; while (size < N) size <<= 1; seg.assign(2 * size, Info()); } void set(int k, const Info &x) { seg[k + size] = x; } void build() { for (int k = size - 1; k > 0; k--) { seg[k] = seg[2 * k] + seg[2 * k + 1]; } } void update(int k, const Info &x) { k += size; seg[k] = x; while (k >>= 1) { seg[k] = seg[2 * k] + seg[2 * k + 1]; } } void add(int k, const Info &x) { k += size; seg[k] += x; while (k >>= 1) { seg[k] = seg[2 * k] + seg[2 * k + 1]; } } // query to [a, b) Info query(int a, int b) { Info L = Info(), R = Info(); for (a += size, b += size; a < b; a >>= 1, b >>= 1) { if (a & 1) L = L + seg[a++]; if (b & 1) R = seg[--b] + R; } return L + R; } Info &operator[](const int &k) { return seg[k + size]; } }; #line 5 "Verify/PointAddRangeSum.test.cpp" struct Info { i64 x = 0; }; Info operator+(const Info& a, const Info& b) { return {a.x + b.x}; } int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, q; std::cin >> n >> q; std::vector<Info> a(n); for (auto&& it : a) std::cin >> it.x; SegmentTree<Info> st(a); while (q--) { int op; std::cin >> op; if (op == 0) { int p, x; std::cin >> p >> x; st.update(p, {st[p].x + x}); } else { int l, r; std::cin >> l >> r; std::cout << st.query(l, r).x << '\n'; } } return 0; }