DataStructure/test/aizu_dsl_2_b_fenwick_aizu.test.cpp

View this file on GitHub
Last update: 2023-01-07 01:54:04+08:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B

Depends on

DataStructure/Fenwick/Fenwick.h

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B"

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

#include "../Fenwick/Fenwick.h"

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, q; cin >> n >> q;
    Fenwick<long long> bit(n);
    while (q--) {
        int typ, x, y; cin >> typ >> x >> y;
        --x;
        if (typ == 0) bit.update(x, y);
        else cout << bit.get(x, y) << '\n';
    }
}

#line 1 "DataStructure/test/aizu_dsl_2_b_fenwick_aizu.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B"

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

#line 1 "DataStructure/Fenwick/Fenwick.h"
// 1D Fenwick {{{
// 0 based index
//
// Tested:
// - https://judge.yosupo.jp/problem/static_range_sum
// - https://judge.yosupo.jp/problem/point_add_range_sum
template<
    typename T  // need to support operators + -
> struct Fenwick {
    Fenwick(int _n) : n(_n), f(_n + 1) {}

    // a[u] += val
    void update(int u, T val) {
        assert(0 <= u && u < n);
        ++u;
        for (; u <= n; u += u & -u) {
            f[u] += val;
        }
    }

    // return a[0] + .. + a[u-1]
    T get(int u) const {
        assert(0 <= u && u <= n);
        T res = 0;
        for (; u > 0; u -= u & -u) {
            res += f[u];
        }
        return res;
    }

    // return a[l] + .. + a[r-1]
    T get(int l, int r) const {
        assert(0 <= l && l <= r && r <= n);
        if (l == r) return 0;  // empty
        return get(r) - get(l);
    }

    void reset() {
        std::fill(f.begin(), f.end(), T(0));
    }

    int n;
    vector<T> f;
};
// }}}
#line 7 "DataStructure/test/aizu_dsl_2_b_fenwick_aizu.test.cpp"

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, q; cin >> n >> q;
    Fenwick<long long> bit(n);
    while (q--) {
        int typ, x, y; cin >> typ >> x >> y;
        --x;
        if (typ == 0) bit.update(x, y);
        else cout << bit.get(x, y) << '\n';
    }
}