diff options
Diffstat (limited to 'meowpp.test/src/BinaryIndexTree.cpp')
-rw-r--r-- | meowpp.test/src/BinaryIndexTree.cpp | 57 |
1 files changed, 57 insertions, 0 deletions
diff --git a/meowpp.test/src/BinaryIndexTree.cpp b/meowpp.test/src/BinaryIndexTree.cpp new file mode 100644 index 0000000..0b81f10 --- /dev/null +++ b/meowpp.test/src/BinaryIndexTree.cpp @@ -0,0 +1,57 @@ +#include "meowpp/dsa/BinaryIndexTree.h" +#include "meowpp/utility.h" + +#include "meowpp.h" + +#include <vector> + +static int N = 100000; + +static std::vector<int> array; + +inline int sum(int k){ + int x = 0; + for(int i = 0; i <= k; i++){ + x += array[i]; + } + return x; +} + +static meow::BinaryIndexTree<int> bit; + +TEST(BinaryIndexTree, "Test with large data"){ + size_t tMe = 0, tBi = 0, t0; + for(int z = 0; z < 10; z++){ + meow::messagePrintf(1, "test %d", z); + bit.reset(N, 0); + array.clear(); + array.resize(N, 0); + + int NN = rand() % 10000; + for(int i = 0; i < NN; i++){ + int index = rand() % N; + if(rand() & 1){ + int val = rand() % 1000; + t0 = clock(); array[i] += val; tMe += clock() - t0; + t0 = clock(); bit.update(i, val); tBi += clock() - t0; + }else{ + if(sum(index) != bit.query(index)){ + meow::messagePrintf(-1, "range-sum query fail"); + return false; + } + } + } + int s = 0; + for(int i = 0; i < N; i++){ + s += array[i]; + if(s != bit.query(i)){ + meow::messagePrintf(-1, "range-sum query fail"); + return false; + } + } + meow::messagePrintf(-1, "ok %.3f/%.3f", + tBi * 1.0 / CLOCKS_PER_SEC, + tMe * 1.0 / CLOCKS_PER_SEC); + } + return true; +}; |