_test/meowpp_BinaryIndexTree.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
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;
};