Verify/PointAddRangeSum.test.cpp

View this file on GitHub
Last update: 2023-02-11 22:28:05+08:00
Problem: https://judge.yosupo.jp/problem/point_add_range_sum

Depends on

Code

#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;
}