Menu
I have searched on internet about implementation of Segment trees but found nothing when it came to lazy propagation. There were some previous questions on stack overflow but they were focused on solving some particular problems of SPOJ. Though I think this is the best explanation of segment trees with pseudocode but I need to implement it with lazy propagation. I found following links :
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Segment_Trees
In addition to the above link, some blogs were also there but they all were giving reference to the same thread.
An example of the application of this data structure would be something like, say I have been given a range of numbers from 1 to n. Now I perform some operations like adding some constant number to a particular range or subtracting some constant number from a particular range. After performing operations I'm supposed to tell the minimum and maximum number in the given number.
An obvious solution would be to perform addition or subtraction to each number in the given range one by one. But this can't be feasible in a situation in which no of operations performed are large.
A better approach would be using Segment Trees with lazy propagation technique. It says instead of performing the update operation on each number individually, just keep track of all the operations until all operations are done. Then finally perform update operation to get the minimum and maximum number in the range.
Example with real data
Suppose I have given the range [1,10] which means numbers are 1,2,3,4,5,6,7,8,9,10. Now suppose I perform an operation which decreases the numbers in the range [3,6] by 4 ,so now numbers will look like 1,2,-1,0,1,2,7,8,9,10. Now I perform another operation which increases the numbers in the range [5,9] by 1, so the number will now look like 1,2,-1,0,2,3,8,9,10,10.
Now if I ask you to tell me the maximum and minimum number then the answer will be :
Maximum = 10
Minimum = -1
This is just a simple example.The actual problem might contain thousands of such addition/subtraction operations.I hope it's clear now.
This is what I have understood so far but I guess there is no unified link on Internet which explains the concept and implementation in a better way.
Can anyone give some good explanation including pseudocode for lazy propagation in segment trees?
Thanks.
623
Lazy propagation is a range update and query optimized implementation of a segment tree that performs both operation O(logN) time. *In short, as the name suggests, the algorithm works on laziness for what is not important at the time. Don't update a node until needed, which will avoid the repeated sharing.
Update a value: We start from the root of the segment tree and add diff to all nodes which have given index in their range. If a node doesn't have a given index in its range, we don't make any changes to that node. Below is the implementation of the above approach: C++
A Segment Tree can be built using recursion (bottom-up approach ). Start with the leaves and go up to the root and update the corresponding changes in the nodes that are in the path from leaves to root. Leaves represent a single element.
Lazy propagation almost always includes some kind of sentry-mechanism. You have to verify that the current node doesn't need to be propagated, and this check should be easy and fast. So there are two possibilities:
I sticked myself to the first. It's very simple to check whether a node in a segmented tree should have child nodes (node->lower_value != node->upper_value), but you would also have to check whether those child node are already built (node->left_child, node->right_child), so I introduced a propagation flag node->propagated:
typedef struct lazy_segment_node{
int lower_value;
int upper_value;
struct lazy_segment_node * left_child;
struct lazy_segment_node * right_child;
unsigned char propagated;
} lazy_segment_node;
To initialize a node we call initialize with a pointer to the node pointer (or NULL) and the desired upper_value/lower_value:
lazy_segment_node * initialize(
lazy_segment_node ** mem,
int lower_value,
int upper_value
){
lazy_segment_node * tmp = NULL;
if(mem != NULL)
tmp = *mem;
if(tmp == NULL)
tmp = malloc(sizeof(lazy_segment_node));
if(tmp == NULL)
return NULL;
tmp->lower_value = lower_value;
tmp->upper_value = upper_value;
tmp->propagated = 0;
tmp->left_child = NULL;
tmp->right_child = NULL;
if(mem != NULL)
*mem = tmp;
return tmp;
}
So far nothing special has been done. This looks like every other generic node creation method. However, in order to create the actual child nodes and set the propagation flags we can use a function which will return a pointer on the same node, but propagates it if needed:
lazy_segment_node * accessErr(lazy_segment_node* node, int * error){
if(node == NULL){
if(error != NULL)
*error = 1;
return NULL;
}
/* if the node has been propagated already return it */
if(node->propagated)
return node;
/* the node doesn't need child nodes, set flag and return */
if(node->upper_value == node->lower_value){
node->propagated = 1;
return node;
}
/* skipping left and right child creation, see code below*/
return node;
}
As you can see, a propagated node will exit the function almost immediately. A not propagated node will instead first check whether it should actually contain child nodes and then create them if needed.
This is actually the lazy-evaluation. You don't create the child nodes until needed. Note that accessErr also provides an additional error interface. If you don't need it use access instead:
lazy_segment_node * access(lazy_segment_node* node){
return accessErr(node,NULL);
}
In order to free those elements you can use a generic node deallocation algorithm:
void free_lazy_segment_tree(lazy_segment_node * root){
if(root == NULL)
return;
free_lazy_segment_tree(root->left_child);
free_lazy_segment_tree(root->right_child);
free(root);
}
The following example will use the functions described above to create a lazy-evaluated segment tree based on the interval [1,10]. You can see that after the first initialization test has no child nodes. By using access you actually generate those child nodes and can get their values (if those child nodes exists by the segmented tree's logic):
#include <stdlib.h>
#include <stdio.h>
typedef struct lazy_segment_node{
int lower_value;
int upper_value;
unsigned char propagated;
struct lazy_segment_node * left_child;
struct lazy_segment_node * right_child;
} lazy_segment_node;
lazy_segment_node * initialize(lazy_segment_node ** mem, int lower_value, int upper_value){
lazy_segment_node * tmp = NULL;
if(mem != NULL)
tmp = *mem;
if(tmp == NULL)
tmp = malloc(sizeof(lazy_segment_node));
if(tmp == NULL)
return NULL;
tmp->lower_value = lower_value;
tmp->upper_value = upper_value;
tmp->propagated = 0;
tmp->left_child = NULL;
tmp->right_child = NULL;
if(mem != NULL)
*mem = tmp;
return tmp;
}
lazy_segment_node * accessErr(lazy_segment_node* node, int * error){
if(node == NULL){
if(error != NULL)
*error = 1;
return NULL;
}
if(node->propagated)
return node;
if(node->upper_value == node->lower_value){
node->propagated = 1;
return node;
}
node->left_child = initialize(NULL,node->lower_value,(node->lower_value + node->upper_value)/2);
if(node->left_child == NULL){
if(error != NULL)
*error = 2;
return NULL;
}
node->right_child = initialize(NULL,(node->lower_value + node->upper_value)/2 + 1,node->upper_value);
if(node->right_child == NULL){
free(node->left_child);
if(error != NULL)
*error = 3;
return NULL;
}
node->propagated = 1;
return node;
}
lazy_segment_node * access(lazy_segment_node* node){
return accessErr(node,NULL);
}
void free_lazy_segment_tree(lazy_segment_node * root){
if(root == NULL)
return;
free_lazy_segment_tree(root->left_child);
free_lazy_segment_tree(root->right_child);
free(root);
}
int main(){
lazy_segment_node * test = NULL;
initialize(&test,1,10);
printf("Lazy evaluation test\n");
printf("test->lower_value: %i\n",test->lower_value);
printf("test->upper_value: %i\n",test->upper_value);
printf("\nNode not propagated\n");
printf("test->left_child: %p\n",test->left_child);
printf("test->right_child: %p\n",test->right_child);
printf("\nNode propagated with access:\n");
printf("access(test)->left_child: %p\n",access(test)->left_child);
printf("access(test)->right_child: %p\n",access(test)->right_child);
printf("\nNode propagated with access, but subchilds are not:\n");
printf("access(test)->left_child->left_child: %p\n",access(test)->left_child->left_child);
printf("access(test)->left_child->right_child: %p\n",access(test)->left_child->right_child);
printf("\nCan use access on subchilds:\n");
printf("access(test->left_child)->left_child: %p\n",access(test->left_child)->left_child);
printf("access(test->left_child)->right_child: %p\n",access(test->left_child)->right_child);
printf("\nIt's possible to chain:\n");
printf("access(access(access(test)->right_child)->right_child)->lower_value: %i\n",access(access(access(test)->right_child)->right_child)->lower_value);
printf("access(access(access(test)->right_child)->right_child)->upper_value: %i\n",access(access(access(test)->right_child)->right_child)->upper_value);
free_lazy_segment_tree(test);
return 0;
}
Lazy evaluation test test->lower_value: 1 test->upper_value: 10 Node not propagated test->left_child: (nil) test->right_child: (nil) Node propagated with access: access(test)->left_child: 0x948e020 access(test)->right_child: 0x948e038 Node propagated with access, but subchilds are not: access(test)->left_child->left_child: (nil) access(test)->left_child->right_child: (nil) Can use access on subchilds: access(test->left_child)->left_child: 0x948e050 access(test->left_child)->right_child: 0x948e068 It's possible to chain: access(access(access(test)->right_child)->right_child)->lower_value: 9 access(access(access(test)->right_child)->right_child)->upper_value: 10
141
if someone's looking for further simple code of lazy propagation without using structures:
(code is self-explanatory)
/**
* In this code we have a very large array called arr, and very large set of operations
* Operation #1: Increment the elements within range [i, j] with value val
* Operation #2: Get max element within range [i, j]
* Build tree: build_tree(1, 0, N-1)
* Update tree: update_tree(1, 0, N-1, i, j, value)
* Query tree: query_tree(1, 0, N-1, i, j)
*/
#include<iostream>
#include<algorithm>
using namespace std;
#include<string.h>
#include<math.h>
#define N 20
#define MAX (1+(1<<6)) // Why? :D
#define inf 0x7fffffff
int arr[N];
int tree[MAX];
int lazy[MAX];
/**
* Build and init tree
*/
void build_tree(int node, int a, int b) {
if(a > b) return; // Out of range
if(a == b) { // Leaf node
tree[node] = arr[a]; // Init value
return;
}
build_tree(node*2, a, (a+b)/2); // Init left child
build_tree(node*2+1, 1+(a+b)/2, b); // Init right child
tree[node] = max(tree[node*2], tree[node*2+1]); // Init root value
}
/**
* Increment elements within range [i, j] with value value
*/
void update_tree(int node, int a, int b, int i, int j, int value) {
if(lazy[node] != 0) { // This node needs to be updated
tree[node] += lazy[node]; // Update it
if(a != b) {
lazy[node*2] += lazy[node]; // Mark child as lazy
lazy[node*2+1] += lazy[node]; // Mark child as lazy
}
lazy[node] = 0; // Reset it
}
if(a > b || a > j || b < i) // Current segment is not within range [i, j]
return;
if(a >= i && b <= j) { // Segment is fully within range
tree[node] += value;
if(a != b) { // Not leaf node
lazy[node*2] += value;
lazy[node*2+1] += value;
}
return;
}
update_tree(node*2, a, (a+b)/2, i, j, value); // Updating left child
update_tree(1+node*2, 1+(a+b)/2, b, i, j, value); // Updating right child
tree[node] = max(tree[node*2], tree[node*2+1]); // Updating root with max value
}
/**
* Query tree to get max element value within range [i, j]
*/
int query_tree(int node, int a, int b, int i, int j) {
if(a > b || a > j || b < i) return -inf; // Out of range
if(lazy[node] != 0) { // This node needs to be updated
tree[node] += lazy[node]; // Update it
if(a != b) {
lazy[node*2] += lazy[node]; // Mark child as lazy
lazy[node*2+1] += lazy[node]; // Mark child as lazy
}
lazy[node] = 0; // Reset it
}
if(a >= i && b <= j) // Current segment is totally within range [i, j]
return tree[node];
int q1 = query_tree(node*2, a, (a+b)/2, i, j); // Query left child
int q2 = query_tree(1+node*2, 1+(a+b)/2, b, i, j); // Query right child
int res = max(q1, q2); // Return final result
return res;
}
int main() {
for(int i = 0; i < N; i++) arr[i] = 1;
build_tree(1, 0, N-1);
memset(lazy, 0, sizeof lazy);
update_tree(1, 0, N-1, 0, 6, 5); // Increment range [0, 6] by 5
update_tree(1, 0, N-1, 7, 10, 12); // Incremenet range [7, 10] by 12
update_tree(1, 0, N-1, 10, N-1, 100); // Increment range [10, N-1] by 100
cout << query_tree(1, 0, N-1, 0, N-1) << endl; // Get max element in range [0, N-1]
}
refer this link for more explanation Segment Trees and lazy propagation
42
Although I haven't successfully solved it yet, I believe this problem is much easier than what we think. You probably don't even need to use Segment Tree/Interval Tree... In fact, I tried both ways of implementing Segment Tree, one uses tree structure and the other uses array, both solutions got TLE quickly. I have a feeling it could be done using Greedy, but I'm not sure yet. Anyway, if you want to see how things are done using Segment Tree, feel free to study my solution. Note that max_tree[1] and min_tree[1] are corresponding to max/min.
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
#include <utility>
#include <stack>
#include <deque>
#include <queue>
#include <fstream>
#include <functional>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#ifdef _WIN32 || _WIN64
#define getc_unlocked _fgetc_nolock
#endif
using namespace std;
const int MAX_RANGE = 1000000;
const int NIL = -(1 << 29);
int data[MAX_RANGE] = {0};
int min_tree[3 * MAX_RANGE + 1];
int max_tree[3 * MAX_RANGE + 1];
int added_to_interval[3 * MAX_RANGE + 1];
struct node {
int max_value;
int min_value;
int added;
node *left;
node *right;
};
node* build_tree(int l, int r, int values[]) {
node *root = new node;
root->added = 0;
if (l > r) {
return NULL;
}
else if (l == r) {
root->max_value = l + 1; // or values[l]
root->min_value = l + 1; // or values[l]
root->added = 0;
root->left = NULL;
root->right = NULL;
return root;
}
else {
root->left = build_tree(l, (l + r) / 2, values);
root->right = build_tree((l + r) / 2 + 1, r, values);
root->max_value = max(root->left->max_value, root->right->max_value);
root->min_value = min(root->left->min_value, root->right->min_value);
root->added = 0;
return root;
}
}
node* build_tree(int l, int r) {
node *root = new node;
root->added = 0;
if (l > r) {
return NULL;
}
else if (l == r) {
root->max_value = l + 1; // or values[l]
root->min_value = l + 1; // or values[l]
root->added = 0;
root->left = NULL;
root->right = NULL;
return root;
}
else {
root->left = build_tree(l, (l + r) / 2);
root->right = build_tree((l + r) / 2 + 1, r);
root->max_value = max(root->left->max_value, root->right->max_value);
root->min_value = min(root->left->min_value, root->right->min_value);
root->added = 0;
return root;
}
}
void update_tree(node* root, int begin, int end, int i, int j, int amount) {
// out of range
if (begin > end || begin > j || end < i) {
return;
}
// in update range (i, j)
else if (i <= begin && end <= j) {
root->max_value += amount;
root->min_value += amount;
root->added += amount;
}
else {
if (root->left == NULL && root->right == NULL) {
root->max_value = root->max_value + root->added;
root->min_value = root->min_value + root->added;
}
else if (root->right != NULL && root->left == NULL) {
update_tree(root->right, (begin + end) / 2 + 1, end, i, j, amount);
root->max_value = root->right->max_value + root->added;
root->min_value = root->right->min_value + root->added;
}
else if (root->left != NULL && root->right == NULL) {
update_tree(root->left, begin, (begin + end) / 2, i, j, amount);
root->max_value = root->left->max_value + root->added;
root->min_value = root->left->min_value + root->added;
}
else {
update_tree(root->right, (begin + end) / 2 + 1, end, i, j, amount);
update_tree(root->left, begin, (begin + end) / 2, i, j, amount);
root->max_value = max(root->left->max_value, root->right->max_value) + root->added;
root->min_value = min(root->left->min_value, root->right->min_value) + root->added;
}
}
}
void print_tree(node* root) {
if (root != NULL) {
print_tree(root->left);
cout << "\t(max, min): " << root->max_value << ", " << root->min_value << endl;
print_tree(root->right);
}
}
void clean_up(node*& root) {
if (root != NULL) {
clean_up(root->left);
clean_up(root->right);
delete root;
root = NULL;
}
}
void update_bruteforce(int x, int y, int z, int &smallest, int &largest, int data[], int n) {
for (int i = x; i <= y; ++i) {
data[i] += z;
}
// update min/max
smallest = data[0];
largest = data[0];
for (int i = 0; i < n; ++i) {
if (data[i] < smallest) {
smallest = data[i];
}
if (data[i] > largest) {
largest = data[i];
}
}
}
void build_tree_as_array(int position, int left, int right) {
if (left > right) {
return;
}
else if (left == right) {
max_tree[position] = left + 1;
min_tree[position] = left + 1;
added_to_interval[position] = 0;
return;
}
else {
build_tree_as_array(position * 2, left, (left + right) / 2);
build_tree_as_array(position * 2 + 1, (left + right) / 2 + 1, right);
max_tree[position] = max(max_tree[position * 2], max_tree[position * 2 + 1]);
min_tree[position] = min(min_tree[position * 2], min_tree[position * 2 + 1]);
}
}
void update_tree_as_array(int position, int b, int e, int i, int j, int value) {
if (b > e || b > j || e < i) {
return;
}
else if (i <= b && e <= j) {
max_tree[position] += value;
min_tree[position] += value;
added_to_interval[position] += value;
return;
}
else {
int left_branch = 2 * position;
int right_branch = 2 * position + 1;
// make sure the array is ok
if (left_branch >= 2 * MAX_RANGE + 1 || right_branch >= 2 * MAX_RANGE + 1) {
max_tree[position] = max_tree[position] + added_to_interval[position];
min_tree[position] = min_tree[position] + added_to_interval[position];
return;
}
else if (max_tree[left_branch] == NIL && max_tree[right_branch] == NIL) {
max_tree[position] = max_tree[position] + added_to_interval[position];
min_tree[position] = min_tree[position] + added_to_interval[position];
return;
}
else if (max_tree[left_branch] != NIL && max_tree[right_branch] == NIL) {
update_tree_as_array(left_branch, b , (b + e) / 2 , i, j, value);
max_tree[position] = max_tree[left_branch] + added_to_interval[position];
min_tree[position] = min_tree[left_branch] + added_to_interval[position];
}
else if (max_tree[right_branch] != NIL && max_tree[left_branch] == NIL) {
update_tree_as_array(right_branch, (b + e) / 2 + 1 , e , i, j, value);
max_tree[position] = max_tree[right_branch] + added_to_interval[position];
min_tree[position] = min_tree[right_branch] + added_to_interval[position];
}
else {
update_tree_as_array(left_branch, b, (b + e) / 2 , i, j, value);
update_tree_as_array(right_branch, (b + e) / 2 + 1 , e , i, j, value);
max_tree[position] = max(max_tree[position * 2], max_tree[position * 2 + 1]) + added_to_interval[position];
min_tree[position] = min(min_tree[position * 2], min_tree[position * 2 + 1]) + added_to_interval[position];
}
}
}
void show_data(int data[], int n) {
cout << "[current data]\n";
for (int i = 0; i < n; ++i) {
cout << data[i] << ", ";
}
cout << endl;
}
inline void input(int* n) {
char c = 0;
while (c < 33) {
c = getc_unlocked(stdin);
}
*n = 0;
while (c > 33) {
*n = (*n * 10) + c - '0';
c = getc_unlocked(stdin);
}
}
void handle_special_case(int m) {
int type;
int x;
int y;
int added_amount;
for (int i = 0; i < m; ++i) {
input(&type);
input(&x);
input(&y);
input(&added_amount);
}
printf("0\n");
}
void find_largest_range_use_tree() {
int n;
int m;
int type;
int x;
int y;
int added_amount;
input(&n);
input(&m);
if (n == 1) {
handle_special_case(m);
return;
}
node *root = build_tree(0, n - 1);
for (int i = 0; i < m; ++i) {
input(&type);
input(&x);
input(&y);
input(&added_amount);
if (type == 1) {
added_amount *= 1;
}
else {
added_amount *= -1;
}
update_tree(root, 0, n - 1, x - 1, y - 1, added_amount);
}
printf("%d\n", root->max_value - root->min_value);
}
void find_largest_range_use_array() {
int n;
int m;
int type;
int x;
int y;
int added_amount;
input(&n);
input(&m);
if (n == 1) {
handle_special_case(m);
return;
}
memset(min_tree, NIL, 3 * sizeof(int) * n + 1);
memset(max_tree, NIL, 3 * sizeof(int) * n + 1);
memset(added_to_interval, 0, 3 * sizeof(int) * n + 1);
build_tree_as_array(1, 0, n - 1);
for (int i = 0; i < m; ++i) {
input(&type);
input(&x);
input(&y);
input(&added_amount);
if (type == 1) {
added_amount *= 1;
}
else {
added_amount *= -1;
}
update_tree_as_array(1, 0, n - 1, x - 1, y - 1, added_amount);
}
printf("%d\n", max_tree[1] - min_tree[1]);
}
void update_slow(int x, int y, int value) {
for (int i = x - 1; i < y; ++i) {
data[i] += value;
}
}
void find_largest_range_use_common_sense() {
int n;
int m;
int type;
int x;
int y;
int added_amount;
input(&n);
input(&m);
if (n == 1) {
handle_special_case(m);
return;
}
memset(data, 0, sizeof(int) * n);
for (int i = 0; i < m; ++i) {
input(&type);
input(&x);
input(&y);
input(&added_amount);
if (type == 1) {
added_amount *= 1;
}
else {
added_amount *= -1;
}
update_slow(x, y, added_amount);
}
// update min/max
int smallest = data[0] + 1;
int largest = data[0] + 1;
for (int i = 1; i < n; ++i) {
if (data[i] + i + 1 < smallest) {
smallest = data[i] + i + 1;
}
if (data[i] + i + 1 > largest) {
largest = data[i] + i + 1;
}
}
printf("%d\n", largest - smallest);
}
void inout_range_of_data() {
int test_cases;
input(&test_cases);
while (test_cases--) {
find_largest_range_use_common_sense();
}
}
namespace unit_test {
void test_build_tree() {
for (int i = 0; i < MAX_RANGE; ++i) {
data[i] = i + 1;
}
node *root = build_tree(0, MAX_RANGE - 1, data);
print_tree(root);
}
void test_against_brute_force() {
// arrange
int number_of_operations = 100;
for (int i = 0; i < MAX_RANGE; ++i) {
data[i] = i + 1;
}
node *root = build_tree(0, MAX_RANGE - 1, data);
// print_tree(root);
// act
int operation;
int x;
int y;
int added_amount;
int smallest = 1;
int largest = MAX_RANGE;
// assert
while (number_of_operations--) {
operation = rand() % 2;
x = 1 + rand() % MAX_RANGE;
y = x + (rand() % (MAX_RANGE - x + 1));
added_amount = 1 + rand() % MAX_RANGE;
// cin >> operation >> x >> y >> added_amount;
if (operation == 1) {
added_amount *= 1;
}
else {
added_amount *= -1;
}
update_bruteforce(x - 1, y - 1, added_amount, smallest, largest, data, MAX_RANGE);
update_tree(root, 0, MAX_RANGE - 1, x - 1, y - 1, added_amount);
assert(largest == root->max_value);
assert(smallest == root->min_value);
for (int i = 0; i < MAX_RANGE; ++i) {
cout << data[i] << ", ";
}
cout << endl << endl;
cout << "correct:\n";
cout << "\t largest = " << largest << endl;
cout << "\t smallest = " << smallest << endl;
cout << "testing:\n";
cout << "\t largest = " << root->max_value << endl;
cout << "\t smallest = " << root->min_value << endl;
cout << "testing:\n";
cout << "\n------------------------------------------------------------\n";
cout << "final result: " << largest - smallest << endl;
cin.get();
}
clean_up(root);
}
void test_automation() {
// arrange
int test_cases;
int number_of_operations = 100;
int n;
test_cases = 10000;
for (int i = 0; i < test_cases; ++i) {
n = i + 1;
int operation;
int x;
int y;
int added_amount;
int smallest = 1;
int largest = n;
// initialize data for brute-force
for (int i = 0; i < n; ++i) {
data[i] = i + 1;
}
// build tree
node *root = build_tree(0, n - 1, data);
for (int i = 0; i < number_of_operations; ++i) {
operation = rand() % 2;
x = 1 + rand() % n;
y = x + (rand() % (n - x + 1));
added_amount = 1 + rand() % n;
if (operation == 1) {
added_amount *= 1;
}
else {
added_amount *= -1;
}
update_bruteforce(x - 1, y - 1, added_amount, smallest, largest, data, n);
update_tree(root, 0, n - 1, x - 1, y - 1, added_amount);
assert(largest == root->max_value);
assert(smallest == root->min_value);
cout << endl << endl;
cout << "For n = " << n << endl;
cout << ", where data is : \n";
for (int i = 0; i < n; ++i) {
cout << data[i] << ", ";
}
cout << endl;
cout << " and query is " << x - 1 << ", " << y - 1 << ", " << added_amount << endl;
cout << "correct:\n";
cout << "\t largest = " << largest << endl;
cout << "\t smallest = " << smallest << endl;
cout << "testing:\n";
cout << "\t largest = " << root->max_value << endl;
cout << "\t smallest = " << root->min_value << endl;
cout << "\n------------------------------------------------------------\n";
cout << "final result: " << largest - smallest << endl;
}
clean_up(root);
}
cout << "DONE............\n";
}
void test_tree_as_array() {
// arrange
int test_cases;
int number_of_operations = 100;
int n;
test_cases = 1000;
for (int i = 0; i < test_cases; ++i) {
n = MAX_RANGE;
memset(min_tree, NIL, sizeof(min_tree));
memset(max_tree, NIL, sizeof(max_tree));
memset(added_to_interval, 0, sizeof(added_to_interval));
memset(data, 0, sizeof(data));
int operation;
int x;
int y;
int added_amount;
int smallest = 1;
int largest = n;
// initialize data for brute-force
for (int i = 0; i < n; ++i) {
data[i] = i + 1;
}
// build tree using array
build_tree_as_array(1, 0, n - 1);
for (int i = 0; i < number_of_operations; ++i) {
operation = rand() % 2;
x = 1 + rand() % n;
y = x + (rand() % (n - x + 1));
added_amount = 1 + rand() % n;
if (operation == 1) {
added_amount *= 1;
}
else {
added_amount *= -1;
}
update_bruteforce(x - 1, y - 1, added_amount, smallest, largest, data, n);
update_tree_as_array(1, 0, n - 1, x - 1, y - 1, added_amount);
//assert(max_tree[1] == largest);
//assert(min_tree[1] == smallest);
cout << endl << endl;
cout << "For n = " << n << endl;
// show_data(data, n);
cout << endl;
cout << " and query is " << x - 1 << ", " << y - 1 << ", " << added_amount << endl;
cout << "correct:\n";
cout << "\t largest = " << largest << endl;
cout << "\t smallest = " << smallest << endl;
cout << "testing:\n";
cout << "\t largest = " << max_tree[1] << endl;
cout << "\t smallest = " << min_tree[1] << endl;
cout << "\n------------------------------------------------------------\n";
cout << "final result: " << largest - smallest << endl;
cin.get();
}
}
cout << "DONE............\n";
}
}
int main() {
// unit_test::test_against_brute_force();
// unit_test::test_automation();
// unit_test::test_tree_as_array();
inout_range_of_data();
return 0;
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
