From 0cebc901e79c21168601071e29ed8e4f4b6f9505 Mon Sep 17 00:00:00 2001 From: Gloria Mundi Date: Sun, 10 Mar 2024 20:43:13 +0100 Subject: add tests for Fenwick Tree --- datastructures/test/fenwickTree2.cpp | 28 ++++++++++++++++++++++++++++ 1 file changed, 28 insertions(+) create mode 100644 datastructures/test/fenwickTree2.cpp (limited to 'datastructures/test/fenwickTree2.cpp') 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 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); +} -- cgit v1.2.3