4 files changed, 90 insertions, 0 deletions
diff --git a/datastructures/test/fenwickTree.cpp b/datastructures/test/fenwickTree.cpp
new file mode 100644
index 0000000..f9dd619
--- /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);
+
+		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..18ebcb7
--- /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);
+
+		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/monotonicConvexHull.cpp b/datastructures/test/monotonicConvexHull.cpp
new file mode 100644
index 0000000..62ea4cd
--- /dev/null
+++ b/datastructures/test/monotonicConvexHull.cpp
@@ -0,0 +1,26 @@
+#include "../monotonicConvexHull.cpp"
+
+int main() {
+	{
+		Envelope env;
+		env.add(10, 0);
+		assert(env.query(0) == 0);
+		assert(env.query(1) == 10);
+		env.add(8, 5);
+		assert(env.query(1) == 10);
+		assert(env.query(2) == 20);
+		assert(env.query(3) == 29);
+		env.add(7, 10);
+		assert(env.query(10) == 80);
+		env.add(0, 0);
+		assert(env.query(11) == 0);
+	}
+
+	{
+		Envelope env;
+		env.add(1, 0);
+		env.add(0, 10);
+		env.add(-1, 10);
+		assert(env.query(7) == 3);
+	}
+}
diff --git a/datastructures/test/persistent.cpp b/datastructures/test/persistent.cpp
new file mode 100644
index 0000000..d98569b
--- /dev/null
+++ b/datastructures/test/persistent.cpp
@@ -0,0 +1,10 @@
+#include "../persistent.cpp"
+
+int main() {
+	int time = 0;
+	persistent<int> p(time, 0);
+	p.set(1);
+	int t1 = time;
+	p.set(2);
+	assert(p.get(t1) == 1);
+}