verify/yosupo/yosupo_point_add_range_sum_segment.test.cpp

• View this file on GitHub
• Last update: 2024-07-23 19:50:25+09:00
• Problem: https://judge.yosupo.jp/problem/point_add_range_sum

Depends on

• data_structure/segment_tree.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"

#include <bits/stdc++.h>
using namespace std;

#include "../../data_structure/segment_tree.hpp"

using S = long long;
S op(S l, S r) { return l + r; }
S e() { return 0; }

int main() {
    int N, Q;
    cin >> N >> Q;
    vector<long long> A(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }

    SegmentTree<S, op, e> seg(A);

    while(Q--) {
        int q;
        cin >> q;
        if(q == 0) {
            long long p, x;
            cin >> p >> x;
            seg.set(p, x + seg.get(p));
        }
        if(q == 1) {
            int l, r;
            cin >> l >> r;
            cout << seg.prod(l, r) << endl;
        } 
    }

    return 0;
}

#line 1 "verify/yosupo/yosupo_point_add_range_sum_segment.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"

#include <bits/stdc++.h>
using namespace std;

#line 1 "data_structure/segment_tree.hpp"
template<class S, S (*op)(S, S), S (*e)()>
struct SegmentTree{
    int n;
    vector<S> data;

    SegmentTree(int sz=0) : n(1) {
        while(n < sz) n *= 2;
        data.resize(2 * n, e());
    }

    SegmentTree(const vector<S> &V) : n(1) {
        int sz = V.size();
        while(n < sz) n *= 2;
        data.resize(2 * n, e());
        for(int i = 0; i < sz; i++) data[i+n] = V[i];
        for(int i = n - 1; i >= 1; i--) data[i] = op(data[i<<1], data[i<<1|1]);
    }

    void set(int i, S x) {
        i += n;
        data[i] = x;
        while(i > 1) {
            i >>= 1;
            data[i] = op(data[i<<1], data[i<<1|1]);
        }
    }

    S prod(int l, int r) {
        l += n; r += n;
        S vl = e(), vr = e();
        while(l < r) {
            if(l & 1) vl = op(vl, data[l++]);
            if(r & 1) vr = op(data[--r], vr);
            l >>= 1; r >>= 1;
        }
        return op(vl, vr);
    }

    S all_prod() { return data[1]; }

    S get(int i) { return data[i + n]; }
};
#line 7 "verify/yosupo/yosupo_point_add_range_sum_segment.test.cpp"

using S = long long;
S op(S l, S r) { return l + r; }
S e() { return 0; }

int main() {
    int N, Q;
    cin >> N >> Q;
    vector<long long> A(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }

    SegmentTree<S, op, e> seg(A);

    while(Q--) {
        int q;
        cin >> q;
        if(q == 0) {
            long long p, x;
            cin >> p >> x;
            seg.set(p, x + seg.get(p));
        }
        if(q == 1) {
            int l, r;
            cin >> l >> r;
            cout << seg.prod(l, r) << endl;
        } 
    }

    return 0;
}

Back to top page