verify/Datastructure_fenwick_tree.test.cpp

View this file on GitHub
Last update: 2025-01-11 20:28:34+09: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 "../Utility/template.hpp"
#include "../Datastructure/fenwick_tree.hpp"

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << fixed << setprecision(15);
    int N;
    cin >> N;
    int Q;
    cin >> Q;
    fenwick_tree<ll> fw(N);
    for(int i = 0; i < N; i++) {
        int a;
        cin >> a;
        fw.add(i, a);
    }

	while(Q--) {
		int t;
		cin >> t;
		if(t==0) {
			ll p, x;
			cin >> p >> x;
            fw.add(p, x);
		}
		else {
			ll l, r;
			cin >> l >> r;
			cout << fw.prod(l, r) << '\n';
		}
	}
}

#line 1 "verify/Datastructure_fenwick_tree.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/point_add_range_sum"
#line 1 "Utility/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define rrep(i, s, t) for (ll i = (ll)(t) - 1; i >= (ll)(s); i--)
#define all(x) begin(x), end(x)

#define TT template <typename T>
TT using vec = vector<T>;
template <class T1, class T2> bool chmin(T1 &x, T2 y) {
    return x > y ? (x = y, true) : false;
}
template <class T1, class T2> bool chmax(T1 &x, T2 y) {
    return x < y ? (x = y, true) : false;
}
struct io_setup {
    io_setup() {
        ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
        cout << fixed << setprecision(15);
    }
} io_setup;

/*
@brief verify用テンプレート
*/
#line 1 "Datastructure/fenwick_tree.hpp"
template <class T> struct fenwick_tree {
  public:
    fenwick_tree() : n(0) {}
    explicit fenwick_tree(int n) : n(n), data(n), raw(n, T()), S(T()) {}

    void add(int p, T x) {
        assert(0 <= p && p < n);
        raw[p] += x;
        S += x;

        p++;
        while (p <= n) {
            data[p - 1] += x;
            p += p & -p;
        }
    }

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

    T prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= n);
        return sum(r) - sum(l);
    }

    T all_prod() const { return S; }

    T get(int p) const { return raw[p]; }

    template <class F> int max_right(F f) const {
        assert(f(0));
        T s = 0;
        int p = 0;
        for (int i = 32 - __builtin_clz(n) - 1; i >= 0; i--) {
            int k = p + (1 << i);
            if (k <= n && f(s + data[k - 1])) {
                s += data[k - 1];
                p = k;
            }
        }
        return p;
    }

  private:
    int n;
    vector<T> data;
    vector<T> raw;
    T S;
};
#line 4 "verify/Datastructure_fenwick_tree.test.cpp"

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << fixed << setprecision(15);
    int N;
    cin >> N;
    int Q;
    cin >> Q;
    fenwick_tree<ll> fw(N);
    for(int i = 0; i < N; i++) {
        int a;
        cin >> a;
        fw.add(i, a);
    }

	while(Q--) {
		int t;
		cin >> t;
		if(t==0) {
			ll p, x;
			cin >> p >> x;
            fw.add(p, x);
		}
		else {
			ll l, r;
			cin >> l >> r;
			cout << fw.prod(l, r) << '\n';
		}
	}
}