test/data-structure/fenwick/aoj-dsl-Range-Sum-Query.test.cpp

View this file on GitHub
Last update: 2023-07-11 10:41:16+08:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B

Depends on

library/data-structure/fenwick.hpp

Code

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

#include <iostream>
#include "../../../library/data-structure/fenwick.hpp"
using namespace std;
using namespace felix;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	fenwick<long long> fenw(n);
	while(q--) {
		int type, x, y;
		cin >> type >> x >> y;
		--x;
		if(type == 0) {
			fenw.add(x, y);
		} else {
			cout << fenw.sum(x, y) << "\n";
		}
	}
	return 0;
}

#line 1 "test/data-structure/fenwick/aoj-dsl-Range-Sum-Query.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B"

#include <iostream>
#line 2 "library/data-structure/fenwick.hpp"
#include <vector>
#include <cassert>

namespace felix {

template<class S>
struct fenwick {
public:
	fenwick() : n(0) {}
	explicit fenwick(int _n) : n(_n), data(_n) {}

	void add(int p, S x) {
		for(int i = p + 1; i <= n; i += i & -i) {
			data[i - 1] += x;
		}
	}

	// [0, p)
	S get(int p) const {
		auto ans = S();
		for(int i = p; i > 0; i -= i & -i) {
			ans += data[i - 1];
		}
		return ans;
	}

	// [l, r)
	S sum(int l, int r) const { return get(r) - get(l); }

	// 0-based
	int kth(S k) const {
		int x = 0;
		for(int i = 1 << std::__lg(n); i > 0; i >>= 1) {
			if (x + i <= n && k >= data[x + i - 1]) {
				x += i;
				k -= data[x - 1];
			}
		}
		return x;
	}

private:
	int n;
	std::vector<S> data;
};

} // namespace felix
#line 5 "test/data-structure/fenwick/aoj-dsl-Range-Sum-Query.test.cpp"
using namespace std;
using namespace felix;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	fenwick<long long> fenw(n);
	while(q--) {
		int type, x, y;
		cin >> type >> x >> y;
		--x;
		if(type == 0) {
			fenw.add(x, y);
		} else {
			cout << fenw.sum(x, y) << "\n";
		}
	}
	return 0;
}