test/datastructure/fenwick_tree/aoj_dsl_2_b.test.cpp

• View this file on GitHub
• Last update: 2024-11-03 14:10:53+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_B

Depends on

• Fenwick Tree (Binary Indexed Tree) (src/datastructure/fenwick_tree.hpp)

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	AC	220 ms	14 MB
g++	00_small_01.in	AC	13 ms	14 MB
g++	00_small_02.in	AC	12 ms	14 MB
g++	00_small_03.in	AC	12 ms	14 MB
g++	01_rand_00.in	AC	12 ms	14 MB
g++	01_rand_01.in	AC	12 ms	14 MB
g++	01_rand_02.in	AC	12 ms	14 MB
g++	01_rand_03.in	AC	13 ms	14 MB
g++	02_slight_00.in	AC	12 ms	14 MB
g++	02_slight_01.in	AC	13 ms	14 MB
g++	02_slight_02.in	AC	16 ms	14 MB
g++	02_slight_03.in	AC	43 ms	14 MB
g++	03_biased_00.in	AC	13 ms	14 MB
g++	03_biased_01.in	AC	92 ms	14 MB
g++	03_biased_02.in	AC	106 ms	14 MB
g++	03_biased_03.in	AC	114 ms	14 MB
g++	04_maximum_00.in	AC	137 ms	15 MB
g++	04_maximum_01.in	AC	126 ms	14 MB
g++	04_maximum_02.in	AC	170 ms	15 MB
g++	04_maximum_03.in	AC	159 ms	15 MB
clang++	00_small_00.in	AC	11 ms	12 MB
clang++	00_small_01.in	AC	11 ms	16 MB
clang++	00_small_02.in	AC	11 ms	16 MB
clang++	00_small_03.in	AC	12 ms	14 MB
clang++	01_rand_00.in	AC	12 ms	12 MB
clang++	01_rand_01.in	AC	12 ms	14 MB
clang++	01_rand_02.in	AC	11 ms	12 MB
clang++	01_rand_03.in	AC	12 ms	14 MB
clang++	02_slight_00.in	AC	12 ms	16 MB
clang++	02_slight_01.in	AC	13 ms	16 MB
clang++	02_slight_02.in	AC	16 ms	16 MB
clang++	02_slight_03.in	AC	45 ms	16 MB
clang++	03_biased_00.in	AC	13 ms	12 MB
clang++	03_biased_01.in	AC	113 ms	12 MB
clang++	03_biased_02.in	AC	121 ms	14 MB
clang++	03_biased_03.in	AC	118 ms	14 MB
clang++	04_maximum_00.in	AC	137 ms	14 MB
clang++	04_maximum_01.in	AC	129 ms	14 MB
clang++	04_maximum_02.in	AC	125 ms	14 MB
clang++	04_maximum_03.in	AC	141 ms	16 MB

Back to top page