test/AOJ-DLS-2-B.test.cpp

• View this file on GitHub
• Last update: 2021-04-08 19:35:44+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_B

Depends on

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

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_B"

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

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

int main() {
    int n, q;
    cin >> n >> q;

    FenwickTree<int> bit(n);

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

#line 1 "test/AOJ-DLS-2-B.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_B"

#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/AOJ-DLS-2-B.test.cpp"

int main() {
    int n, q;
    cin >> n >> q;

    FenwickTree<int> bit(n);

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

Back to top page