test/datastructure/segment_tree/aoj_dsl_2_b.test.cpp

• View this file on GitHub
• Last update: 2023-12-14 18:25:11+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_B

Depends on

• Segment tree (src/datastructure/segment_tree.hpp)

Code

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

#include "src/datastructure/segment_tree.hpp"

#include <iostream>

using namespace std;

int main() {
	int n, q;
	cin >> n >> q;
	SegmentTree seg([](long long a, long long b) { return a + b; }, 0LL);
	seg.init(n);
	while (q--) {
		int com, x, y;
		cin >> com >> x >> y;
		--x;
		if (com) --y, cout << seg.find(x, y + 1) << endl;
		else seg.update(x, seg.at(x) + y);
	}

	return 0;
}

#line 1 "test/datastructure/segment_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/segment_tree.hpp"



#include <vector>

template<class T, class F>
class SegmentTree { // 0-indexed
private:
	int n_{};
	std::vector<T> tree;
	F f; // function<T(T, T)>
	T ti;

public:
	SegmentTree(F f, T ti) : f(f), ti(ti) {}

	void init(int n) {
		n_ = 1;
		while (n_ < n) n_ *= 2;
		tree.assign(2 * n_, ti);
	}

	void build(std::vector<T> const &v) {
		int const N = v.size();
		init(N);
		for (int i = 0; i < N; ++i) tree[n_ + i] = v[i];
		for (int i = n_ - 1; i > 0; --i) tree[i] = f(tree[2 * i], tree[2 * i + 1]);
	}

	void update(int i, T const &x) {
		i += n_;
		tree[i] = x;
		while (i >>= 1) tree[i] = f(tree[2 * i], tree[2 * i + 1]);
	}

	T find(int l, int r) { // [l, r)
		l += n_, r += n_;
		T ll = ti, rr = ti;
		while (l < r) {
			if (l & 1) ll = f(ll, tree[l++]);
			if (r & 1) rr = f(tree[--r], rr);
			l >>= 1, r >>= 1;
		}
		return f(ll, rr);
	}

	T at(int i) { return tree[i + n_]; }
};


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

#include <iostream>

using namespace std;

int main() {
	int n, q;
	cin >> n >> q;
	SegmentTree seg([](long long a, long long b) { return a + b; }, 0LL);
	seg.init(n);
	while (q--) {
		int com, x, y;
		cin >> com >> x >> y;
		--x;
		if (com) --y, cout << seg.find(x, y + 1) << endl;
		else seg.update(x, seg.at(x) + y);
	}

	return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_small_00.in	AC	13 ms	7 MB
g++	00_small_01.in	AC	20 ms	7 MB
g++	00_small_02.in	AC	16 ms	7 MB
g++	00_small_03.in	AC	13 ms	7 MB
g++	01_rand_00.in	AC	12 ms	7 MB
g++	01_rand_01.in	AC	12 ms	7 MB
g++	01_rand_02.in	AC	12 ms	7 MB
g++	01_rand_03.in	AC	12 ms	7 MB
g++	02_slight_00.in	AC	13 ms	7 MB
g++	02_slight_01.in	AC	13 ms	7 MB
g++	02_slight_02.in	AC	15 ms	7 MB
g++	02_slight_03.in	AC	37 ms	7 MB
g++	03_biased_00.in	AC	14 ms	7 MB
g++	03_biased_01.in	AC	97 ms	8 MB
g++	03_biased_02.in	AC	105 ms	8 MB
g++	03_biased_03.in	AC	118 ms	8 MB
g++	04_maximum_00.in	AC	155 ms	9 MB
g++	04_maximum_01.in	AC	140 ms	9 MB
g++	04_maximum_02.in	AC	147 ms	9 MB
g++	04_maximum_03.in	AC	180 ms	9 MB
clang++	00_small_00.in	AC	12 ms	11 MB
clang++	00_small_01.in	AC	12 ms	13 MB
clang++	00_small_02.in	AC	12 ms	11 MB
clang++	00_small_03.in	AC	12 ms	9 MB
clang++	01_rand_00.in	AC	12 ms	11 MB
clang++	01_rand_01.in	AC	11 ms	9 MB
clang++	01_rand_02.in	AC	12 ms	11 MB
clang++	01_rand_03.in	AC	12 ms	15 MB
clang++	02_slight_00.in	AC	11 ms	7 MB
clang++	02_slight_01.in	AC	12 ms	13 MB
clang++	02_slight_02.in	AC	14 ms	15 MB
clang++	02_slight_03.in	AC	40 ms	8 MB
clang++	03_biased_00.in	AC	12 ms	13 MB
clang++	03_biased_01.in	AC	160 ms	12 MB
clang++	03_biased_02.in	AC	162 ms	8 MB
clang++	03_biased_03.in	AC	123 ms	12 MB
clang++	04_maximum_00.in	AC	141 ms	12 MB
clang++	04_maximum_01.in	AC	152 ms	14 MB
clang++	04_maximum_02.in	AC	254 ms	16 MB
clang++	04_maximum_03.in	AC	183 ms	14 MB

Back to top page