-
Notifications
You must be signed in to change notification settings - Fork 0
/
binary_index_tree_test.cpp
33 lines (32 loc) · 1.11 KB
/
binary_index_tree_test.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
//
// Created by Pankaj Birat on 12/12/18.
//
#include "../../../datastructure/range-query/binary_index_tree.hpp"
class binary_index_tree_test {
public:
void test() {
srand(time(NULL));
int sz = rand() % 100000 + 100;
vector<int> vec;
vec.reserve(sz);
for(int i = 0; i < sz; i++) vec.push_back((rand()%10000000));
binary_index_tree<int> binaryIndexTree(vec);
cout << "Starting Random 1000 test cases mix of update and query" << endl;
for(int i = 0; i < 1000; i++){
int left = rand() % sz;
int right = rand() % sz;
if(left > right) swap(left, right);
int bl = rand() % 2;
if(bl) {
int res = binaryIndexTree.query(left, right);
int sum = accumulate(vec.begin() + left, vec.begin()+right+1, 0);
assert(sum == res);
}else {
int tmp = right + rand() % 10000000;
vec[left] += tmp;
binaryIndexTree.update(left, tmp);
}
}
cout << "All test case successfully passed" << endl;
}
};