test/yosupo-point-add-range-sum.test.cpp

• View this file on GitHub
• Last update: 2021-04-08 19:35:44+09:00
• Problem: https://judge.yosupo.jp/problem/point_add_range_sum

Depends on

• Fenwick-Tree (segtree/fenwick-tree.cpp)

Code

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

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

#include "../segtree/fenwick-tree.cpp"

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int n, q;
    cin >> n >> q;
    FenwickTree<int64_t> bit(n);

    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;
        bit.add(i, a);
    }

    for(int i = 0; i < q; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        if(a)
            cout << bit.sum(b, c) << "\n";
        else
            bit.add(b, c);
    }

    return 0;
}

#line 1 "test/yosupo-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 "segtree/fenwick-tree.cpp"

#line 4 "segtree/fenwick-tree.cpp"
using namespace std;

template <typename T>
class FenwickTree {
private:
    int _n;
    vector<T> data;

    T sum(int r) {
        T s = 0;
        while(r > 0) {
            s += data[r - 1];
            r -= r & -r;
        }
        return s;
    }

public:
    FenwickTree() = default;
    explicit FenwickTree(int n) : _n(n), data(n) {}

    void add(int p, T x) {
        assert(0 <= p && p < _n);
        p++;
        while(p <= _n) {
            data[p - 1] += x;
            p += p & -p;
        }
    }

    T sum(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        return sum(r) - sum(l);
    }
};
/*
 * @brief Fenwick-Tree
 * @docs docs/fenwick-tree.md
 */
#line 7 "test/yosupo-point-add-range-sum.test.cpp"

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int n, q;
    cin >> n >> q;
    FenwickTree<int64_t> bit(n);

    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;
        bit.add(i, a);
    }

    for(int i = 0; i < q; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        if(a)
            cout << bit.sum(b, c) << "\n";
        else
            bit.add(b, c);
    }

    return 0;
}

Back to top page