add BIT

1 files changed, 54 insertions, 0 deletions

diff --git a/_test/meowpp_BinaryIndexTree.cpp b/_test/meowpp_BinaryIndexTree.cpp
new file mode 100644
index 0000000..3841a84
--- /dev/null
+++ b/_test/meowpp_BinaryIndexTree.cpp
@@ -0,0 +1,54 @@
+#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){
+  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;
+};