12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364 |
- #include <bits/stdc++.h>
- using namespace std;
- #define INF 1000000000
- #include "SegmentTree.cpp"
- int main() {
- int values[] = {1,2,3,4,5,6,7};
- build(sizeof(values)/sizeof(int), values);
- assert(query(1,5) == make_pair(2, 14));
- assert(query(0,5) == make_pair(1, 15));
- assert(query(2,8) == make_pair(3, 25));
- assert(query(4,5) == make_pair(5, 5));
- update_range(0, 7, 1);
- assert(query(1,5) == make_pair(3, 18));
- assert(query(0,7) == make_pair(2, 35));
- assert(query(2,8) == make_pair(4, 30));
- assert(query(4,5) == make_pair(6, 6));
- update_range(2, 6, 2);
- update_range(3, 7, 2);
- assert(query(1,5) == make_pair(3, 28));
- assert(query(0,7) == make_pair(2, 51));
- assert(query(2,8) == make_pair(6, 46));
- assert(query(4,5) == make_pair(10, 10));
- assert(query(5,7) == make_pair(10, 21));
- update(2, 0);
- assert(query(1,5) == make_pair(0, 22));
- assert(query(0,7) == make_pair(0, 45));
- assert(query(2,8) == make_pair(0, 40));
- assert(query(4,5) == make_pair(10, 10));
- assert(query(5,7) == make_pair(10, 21));
- update_range(1, 4, 2);
- assert(query(1,5) == make_pair(2, 28));
- assert(query(0,7) == make_pair(2, 51));
- assert(query(4,8) == make_pair(10, 31));
- assert(query(4,5) == make_pair(10, 10));
- assert(query(6,7) == make_pair(10, 10));
- assert(query(1,3) == make_pair(2, 7));
- update(5, -1);
- assert(query(0, 5) == make_pair(2, 30));
- assert(query(6, 7) == make_pair(10, 10));
- assert(query(5, 6) == make_pair(-1, -1));
- assert(query(4, 7) == make_pair(-1, 19));
- update(5, 3);
- update_range(4, 7, 1);
- assert(query(4, 7) == make_pair(4, 26));
- assert(query(0, 7) == make_pair(2, 46));
- delete[] tree;
- int values2[] = {4};
- build(sizeof(values2)/sizeof(int), values2);
- assert(query(0,1) == make_pair(4, 4));
- update(0, 2);
- assert(query(0,1) == make_pair(2, 2));
- update_range(0, 1, 7);
- assert(query(0,1) == make_pair(9, 9));
- update(0, 3);
- assert(query(0,1) == make_pair(3, 3));
- update_range(0, 1, 7);
- update(0, 3);
- assert(query(0,1) == make_pair(3, 3));
- delete[] tree;
- return 0;
- }
|