path: root/_test/meowpp_BinaryIndexTree.cpp

#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;
};