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/fenwickTree.cpp | 26 ++++++++++++++++++++++++++ 1 file changed, 26 insertions(+) create mode 100644 datastructures/test/fenwickTree.cpp (limited to 'datastructures/test/fenwickTree.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 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); +} -- cgit v1.2.3