add tests for Fenwick Tree

5 files changed, 83 insertions, 8 deletions

diff --git a/Makefile b/Makefile
index 10adf28..2e05265 100644
--- a/Makefile
+++ b/Makefile
@@ -1,4 +1,8 @@
-TESTS = graph/test/binary_lifting.test graph/test/LCA_sparse.test
+TESTS = \
+	datastructures/test/fenwickTree.test \
+	datastructures/test/fenwickTree2.test \
+	graph/test/binary_lifting.test \
+	graph/test/LCA_sparse.test
 
 pdf:
 	latexmk -pdf tcr
@@ -23,6 +27,10 @@ cleantest:
 	g++ -include test.h -std=gnu++20 -Wall -Wextra -Wpedantic -Werror \
 		-fsanitize=address,undefined -g -o $@ $<
 
+datastructures/test/fenwickTree.test: datastructures/test/fenwickTree.cpp \
+	datastructures/fenwickTree.cpp
+datastructures/test/fenwickTree2.test: datastructures/test/fenwickTree2.cpp \
+	datastructures/fenwickTree2.cpp
 graph/test/binary_lifting.test: graph/test/binary_lifting.cpp \
 	graph/binary_lifting.cpp graph/test/util.cpp
 graph/test/LCA_sparse.test: graph/test/LCA_sparse.cpp \
diff --git a/datastructures/test/fenwickTree.cpp b/datastructures/test/fenwickTree.cpp
new file mode 100644
index 0000000..4bc812a
--- /dev/null
+++ b/datastructures/test/fenwickTree.cpp
@@ -0,0 +1,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);
+}
diff --git a/datastructures/test/fenwickTree2.cpp b/datastructures/test/fenwickTree2.cpp
new file mode 100644
index 0000000..359a5c4
--- /dev/null
+++ b/datastructures/test/fenwickTree2.cpp
@@ -0,0 +1,28 @@
+#include "../fenwickTree2.cpp"
+
+void test(int n) {
+	vector<ll> naive(n);
+	for (int i = 0; i < n; i++) naive[i] = util::randint();
+	init(naive);
+
+	for (int i = 0; i < 1000; i++) {
+		int l = util::randint(n), r = util::randint(n);
+		if (l > r) swap(l, r);
+		ll delta = util::randint();
+		update(l, r, delta);
+		for (int i = l; i < r; i++) naive[i] += delta;
+
+		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);
+}
diff --git a/graph/test/util.cpp b/graph/test/util.cpp
index 8bec1ee..8c14b5c 100644
--- a/graph/test/util.cpp
+++ b/graph/test/util.cpp
@@ -1,13 +1,6 @@
 
 namespace util {
 
-mt19937 rd(0);
-
-int randint(int x) {
-	assert(x > 0);
-	return uniform_int_distribution<int>(0, x-1)(rd);
-}
-
 void shuffle_adj_lists(vector<vector<int>> &adj) {
 	for (auto &a: adj) ranges::shuffle(a, rd);
 }
diff --git a/test.h b/test.h
index cca2243..ce2689f 100644
--- a/test.h
+++ b/test.h
@@ -11,3 +11,23 @@ T _lg_check(T n) {
 }
 
 #define __lg _lg_check
+
+namespace util {
+
+mt19937 rd(0);
+
+int randint(int l, int r) {
+	assert(l <= r);
+	return uniform_int_distribution<int>(l, r)(rd);
+}
+
+int randint(int x) {
+	assert(x > 0);
+	return randint(0, x-1);
+}
+
+int randint() {
+	return randint(-1'000'000, +1'000'000);
+}
+
+}