datastructures/test/fenwickTree.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include "../fenwickTree.cpp"

void test(int n) {
	vector<ll> naive(n);
	init(n);

	for (int i = 0; i < 1000; i++) {
		int p = util::randint(n);
		ll delta = util::randint();
		update(p, delta);
		naive[p] += delta;

		int r = util::randint(n+1) - 1;

		ll naive_result = 0;
		for (int i = 0; i <= r; i++) naive_result += naive[i];
		ll fenwick_result = prefix_sum(r);
		assert(naive_result == fenwick_result);
	}
}

int main() {
	test(1);
	test(100);
	test(1000);
}