test/aoj/DSL_2_B.test.cpp

View this file on GitHub
Last update: 2021-02-13 18:30:55+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B

Depends on

src/FenwickTree.hpp

Code

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

#include "../../src/FenwickTree.hpp"

#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;
using lint = long long;

struct init {
	init() {
		cin.tie(nullptr); ios::sync_with_stdio(false);
		cout << fixed << setprecision(10);
	}
} init_;

int main() {

	int n, q;
	cin >> n >> q;

	FenwickTree<lint> ft(n, 0);
	vector<int> ans;
	for (int i = 0; i < q; i++) {
		int c, x, y;
		cin >> c >> x >> y;
		x--;
		if (c) {
			ans.emplace_back(ft.sum(x, y));
		}
		else {
			ft.add(x, y);
		}
	}

	for (const auto& e : ans) cout << e << "\n";
	
	return 0;
}

#line 1 "test/aoj/DSL_2_B.test.cpp"

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

#line 2 "src/FenwickTree.hpp"

#include <vector>

using namespace std;

template<class T>
class FenwickTree {
public:
    explicit FenwickTree(int sz, T &&x = T{}) : n(sz), bit(n + 1) {
        for (int i = 0; i < n; i++) add(i, x);
    }

    void add(int k, const T &x) { for (; k < n; k |= k + 1) bit[k] += x; }
    void set(int k, const T &x) { add(k, x - sum(k, k + 1)); }

    [[nodiscard]] T sum(int k) const {
        T res = 0;
        for (k--; k >= 0; k = (k & (k + 1)) - 1) res += bit[k];
        return res;
    }
    [[nodiscard]] T sum(int l, int r) const { return sum(r) - sum(l); }

private:
    int n;
    vector<T> bit;
};
#line 5 "test/aoj/DSL_2_B.test.cpp"

#include <iostream>
#include <iomanip>
#line 9 "test/aoj/DSL_2_B.test.cpp"

using namespace std;
using lint = long long;

struct init {
	init() {
		cin.tie(nullptr); ios::sync_with_stdio(false);
		cout << fixed << setprecision(10);
	}
} init_;

int main() {

	int n, q;
	cin >> n >> q;

	FenwickTree<lint> ft(n, 0);
	vector<int> ans;
	for (int i = 0; i < q; i++) {
		int c, x, y;
		cin >> c >> x >> y;
		x--;
		if (c) {
			ans.emplace_back(ft.sum(x, y));
		}
		else {
			ft.add(x, y);
		}
	}

	for (const auto& e : ans) cout << e << "\n";
	
	return 0;
}