This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum" #include <iostream> #include "library/datastructure/segment_tree/segment_tree_2d.hpp" using suisen::SegmentTree2D; long long op(long long x, long long y) { return x + y; } long long e() { return 0; } constexpr int L = 25; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, q; std::cin >> n >> q; std::vector<std::vector<long long>> a(L, std::vector<long long>(n)); for (int i = 0; i < n; ++i) { long long v; std::cin >> v; for (int j = 0; j < L; ++j) a[j][i] = v & (3LL << (2 * j)); } SegmentTree2D<long long, op, e> seg(a); while (q --> 0) { int t; std::cin >> t; if (t == 0) { int p, x; std::cin >> p >> x; long long val = seg(0, L, p, p + 1) + x; for (int j = 0; j < L; ++j) { seg.set(j, p, val & (3LL << (2 * j))); } } else { int l, r; std::cin >> l >> r; std::cout << seg(0, L, l, r) << '\n'; } } return 0; }
#line 1 "test/src/datastructure/segment_tree/segment_tree_2d/point_add_range_sum.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum" #include <iostream> #line 1 "library/datastructure/segment_tree/segment_tree_2d.hpp" #include <cassert> #include <vector> namespace suisen { template <typename T, T(*op)(T, T), T(*e)()> struct SegmentTree2D { SegmentTree2D() = default; SegmentTree2D(int n, int m) : SegmentTree2D(std::vector(2 * n, std::vector(2 * m, e()))) {} SegmentTree2D(const std::vector<std::vector<T>> &a) : n(a.size()), m(n == 0 ? 0 : a[0].size()), dat(2 * n, std::vector<T>(2 * m, e())) { for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) { dat[n + i][m + j] = a[i][j]; } for (int i = 1; i < 2 * n; ++i) for (int j = m - 1; j > 0; --j) { dat[i][j] = op(dat[i][2 * j + 0], dat[i][2 * j + 1]); } for (int i = n - 1; i > 0; --i) for (int j = 1; j < 2 * m; ++j) { dat[i][j] = op(dat[2 * i + 0][j], dat[2 * i + 1][j]); } } T operator()(int u, int d, int l, int r) const { assert(0 <= u and u <= d and d <= n and 0 <= l and l <= r and r <= m); auto inner_query = [&](const auto &seg) { T res_l = e(), res_r = e(); for (int tl = l + m, tr = r + m; tl < tr; tl >>= 1, tr >>= 1) { if (tl & 1) res_l = op(res_l, seg[tl++]); if (tr & 1) res_r = op(seg[--tr], res_r); } return op(res_l, res_r); }; T res_u = e(), res_d = e(); for (int tu = u + n, td = d + n; tu < td; tu >>= 1, td >>= 1) { if (tu & 1) res_u = op(res_u, inner_query(dat[tu++])); if (td & 1) res_d = op(inner_query(dat[--td]), res_d); } return op(res_u, res_d); } T get(int i, int j) const { assert(0 <= i and i < n and 0 <= j and j < m); return dat[n + i][m + j]; } void set(int i, int j, const T &val) { assert(0 <= i and i < n and 0 <= j and j < m); dat[n + i][m + j] = val; for (int tj = (m + j) >> 1; tj; tj >>= 1) { dat[n + i][tj] = op(dat[n + i][2 * tj + 0], dat[n + i][2 * tj + 1]); } for (int ti = (n + i) >> 1; ti; ti >>= 1) { for (int tj = m + j; tj; tj >>= 1) { dat[ti][tj] = op(dat[2 * ti + 0][tj], dat[2 * ti + 1][tj]); } } } private: int n, m; std::vector<std::vector<T>> dat; }; } #line 6 "test/src/datastructure/segment_tree/segment_tree_2d/point_add_range_sum.test.cpp" using suisen::SegmentTree2D; long long op(long long x, long long y) { return x + y; } long long e() { return 0; } constexpr int L = 25; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, q; std::cin >> n >> q; std::vector<std::vector<long long>> a(L, std::vector<long long>(n)); for (int i = 0; i < n; ++i) { long long v; std::cin >> v; for (int j = 0; j < L; ++j) a[j][i] = v & (3LL << (2 * j)); } SegmentTree2D<long long, op, e> seg(a); while (q --> 0) { int t; std::cin >> t; if (t == 0) { int p, x; std::cin >> p >> x; long long val = seg(0, L, p, p + 1) + x; for (int j = 0; j < L; ++j) { seg.set(j, p, val & (3LL << (2 * j))); } } else { int l, r; std::cin >> l >> r; std::cout << seg(0, L, l, r) << '\n'; } } return 0; }