:heavy_check_mark: test/datastructure/fenwick_tree/aoj_dsl_2_b.test.cpp

Depends on

Code

// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_B

#include "src/datastructure/fenwick_tree.hpp"

#include <iostream>

using namespace std;

int main() {
	int n, q;
	cin >> n >> q;
	FenwickTree<int> ft(n);
	while (q--) {
		int com, x, y;
		cin >> com >> x >> y;
		if (com) cout << ft.find(x - 1, y) << endl;
		else ft.add(x - 1, y);
	}

	return 0;
}
#line 1 "test/datastructure/fenwick_tree/aoj_dsl_2_b.test.cpp"
// verification-helper: PROBLEM https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_B

#line 1 "src/datastructure/fenwick_tree.hpp"



#include <vector>

template<class T>
class FenwickTree {
private:
	int n;
	std::vector<T> tree;

public:
	FenwickTree(int n) : n(n), tree(n) {}

	void add(int i, T x) {
		++i;
		while (i <= n) {
			tree[i - 1] += x;
			i += i & -i;
		}
	}

	T sum(int i) { // [0, i)
		T s{0};
		while (i > 0) {
			s += tree[i - 1];
			i -= i & -i;
		}
		return s;
	}

	T find(int l, int r) { // [l, r)
		return sum(r) - sum(l);
	}
};


#line 4 "test/datastructure/fenwick_tree/aoj_dsl_2_b.test.cpp"

#include <iostream>

using namespace std;

int main() {
	int n, q;
	cin >> n >> q;
	FenwickTree<int> ft(n);
	while (q--) {
		int com, x, y;
		cin >> com >> x >> y;
		if (com) cout << ft.find(x - 1, y) << endl;
		else ft.add(x - 1, y);
	}

	return 0;
}

Test cases

Env Name Status Elapsed Memory
g++ 00_small_00.in :heavy_check_mark: AC 220 ms 14 MB
g++ 00_small_01.in :heavy_check_mark: AC 13 ms 14 MB
g++ 00_small_02.in :heavy_check_mark: AC 12 ms 14 MB
g++ 00_small_03.in :heavy_check_mark: AC 12 ms 14 MB
g++ 01_rand_00.in :heavy_check_mark: AC 12 ms 14 MB
g++ 01_rand_01.in :heavy_check_mark: AC 12 ms 14 MB
g++ 01_rand_02.in :heavy_check_mark: AC 12 ms 14 MB
g++ 01_rand_03.in :heavy_check_mark: AC 13 ms 14 MB
g++ 02_slight_00.in :heavy_check_mark: AC 12 ms 14 MB
g++ 02_slight_01.in :heavy_check_mark: AC 13 ms 14 MB
g++ 02_slight_02.in :heavy_check_mark: AC 16 ms 14 MB
g++ 02_slight_03.in :heavy_check_mark: AC 43 ms 14 MB
g++ 03_biased_00.in :heavy_check_mark: AC 13 ms 14 MB
g++ 03_biased_01.in :heavy_check_mark: AC 92 ms 14 MB
g++ 03_biased_02.in :heavy_check_mark: AC 106 ms 14 MB
g++ 03_biased_03.in :heavy_check_mark: AC 114 ms 14 MB
g++ 04_maximum_00.in :heavy_check_mark: AC 137 ms 15 MB
g++ 04_maximum_01.in :heavy_check_mark: AC 126 ms 14 MB
g++ 04_maximum_02.in :heavy_check_mark: AC 170 ms 15 MB
g++ 04_maximum_03.in :heavy_check_mark: AC 159 ms 15 MB
clang++ 00_small_00.in :heavy_check_mark: AC 11 ms 12 MB
clang++ 00_small_01.in :heavy_check_mark: AC 11 ms 16 MB
clang++ 00_small_02.in :heavy_check_mark: AC 11 ms 16 MB
clang++ 00_small_03.in :heavy_check_mark: AC 12 ms 14 MB
clang++ 01_rand_00.in :heavy_check_mark: AC 12 ms 12 MB
clang++ 01_rand_01.in :heavy_check_mark: AC 12 ms 14 MB
clang++ 01_rand_02.in :heavy_check_mark: AC 11 ms 12 MB
clang++ 01_rand_03.in :heavy_check_mark: AC 12 ms 14 MB
clang++ 02_slight_00.in :heavy_check_mark: AC 12 ms 16 MB
clang++ 02_slight_01.in :heavy_check_mark: AC 13 ms 16 MB
clang++ 02_slight_02.in :heavy_check_mark: AC 16 ms 16 MB
clang++ 02_slight_03.in :heavy_check_mark: AC 45 ms 16 MB
clang++ 03_biased_00.in :heavy_check_mark: AC 13 ms 12 MB
clang++ 03_biased_01.in :heavy_check_mark: AC 113 ms 12 MB
clang++ 03_biased_02.in :heavy_check_mark: AC 121 ms 14 MB
clang++ 03_biased_03.in :heavy_check_mark: AC 118 ms 14 MB
clang++ 04_maximum_00.in :heavy_check_mark: AC 137 ms 14 MB
clang++ 04_maximum_01.in :heavy_check_mark: AC 129 ms 14 MB
clang++ 04_maximum_02.in :heavy_check_mark: AC 125 ms 14 MB
clang++ 04_maximum_03.in :heavy_check_mark: AC 141 ms 16 MB
Back to top page