How to update a range in a segment tree while maintaining max and min?

Question

I am implementing a segment tree from a data array, and also want to support the max / min tree when updating a data range. Here is my initial approach after this tutorial http://p--np.blogspot.com/2011/07/segment-tree.html . Unfortunately, this does not work at all, the logic makes sense to me, but I'm a little confused in b and e , I wonder if this is the range of the data array? or is it the actual range of the tree? As far as I understand, max_segment_tree[1] should contain the max range [1, MAX_RANGE] , and min_segment_tree[1] should contain the min range [1, MAX_RANGE] .

 int data[MAX_RANGE]; int max_segment_tree[3 * MAX_RANGE + 1]; int min_segment_tree[3 * MAX_RANGE + 1]; void build_tree(int position, int left, int right) { if (left > right) { return; } else if (left == right) { max_segment_tree[position] = data[left]; min_segment_tree[position] = data[left]; return; } int middle = (left + right) / 2; build_tree(position * 2, left, middle); build_tree(position * 2 + 1, middle + 1, right); max_segment_tree[position] = max(max_segment_tree[position * 2], max_segment_tree[position * 2 + 1]); min_segment_tree[position] = min(min_segment_tree[position * 2], min_segment_tree[position * 2 + 1]); } void update_tree(int position, int b, int e, int i, int j, int value) { if (b > e || b > j || e < i) { return; } if (i <= b && j >= e) { max_segment_tree[position] += value; min_segment_tree[position] += value; return; } update_tree(position * 2 , b , (b + e) / 2 , i, j, value); update_tree(position * 2 + 1 , (b + e) / 2 + 1 , e , i, j, value); max_segment_tree[position] = max(max_segment_tree[position * 2], max_segment_tree[position * 2 + 1]); min_segment_tree[position] = min(min_segment_tree[position * 2], min_segment_tree[position * 2 + 1]); } 

EDIT Adding test cases:

 #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> using namespace std; const int MAX_RANGE = 20; int data[MAX_RANGE]; int max_segment_tree[2 * MAX_RANGE]; int min_segment_tree[2 * MAX_RANGE]; int added_to_interval[2 * MAX_RANGE] = {0}; void update_bruteforce(int x, int y, int z, int &smallest, int &largest) { for (int i = x - 1; i < y; ++i) { data[i] += z; } // update min/max smallest = data[0]; largest = data[0]; for (int i = 0; i < MAX_RANGE; ++i) { if (data[i] < smallest) { smallest = data[i]; } if (data[i] > largest) { largest = data[i]; } } } void build_tree(int position, int left, int right) { if (left > right) { return; } else if (left == right) { max_segment_tree[position] = data[left]; min_segment_tree[position] = data[left]; return; } int middle = (left + right) / 2; build_tree(position * 2, left, middle); build_tree(position * 2 + 1, middle + 1, right); max_segment_tree[position] = max(max_segment_tree[position * 2], max_segment_tree[position * 2 + 1]); min_segment_tree[position] = min(min_segment_tree[position * 2], min_segment_tree[position * 2 + 1]); } void update_tree(int position, int b, int e, int i, int j, int value) { if (b > e || b > j || e < i) { return; } if (i <= b && e <= j) { max_segment_tree[position] += value; min_segment_tree[position] += value; added_to_interval[position] += value; return; } update_tree(position * 2 , b , (b + e) / 2 , i, j, value); update_tree(position * 2 + 1 , (b + e) / 2 + 1 , e , i, j, value); max_segment_tree[position] = max(max_segment_tree[position * 2], max_segment_tree[position * 2 + 1]) + added_to_interval[position]; min_segment_tree[position] = min(min_segment_tree[position * 2], min_segment_tree[position * 2 + 1]) + added_to_interval[position]; } void update(int x, int y, int value) { // memset(added_to_interval, 0, sizeof(added_to_interval)); update_tree(1, 0, MAX_RANGE - 1, x - 1, y - 1, value); } namespace unit_test { void test_show_data() { for (int i = 0; i < MAX_RANGE; ++i) { cout << data[i] << ", "; } cout << endl << endl; } void test_brute_force_and_segment_tree() { // arrange int number_of_operations = 100; for (int i = 0; i < MAX_RANGE; ++i) { data[i] = i + 1; } build_tree(1, 0, MAX_RANGE - 1); // act int operation; int x; int y; int z; int smallest = 1; int largest = MAX_RANGE; // assert while (number_of_operations--) { operation = rand() % 1; x = 1 + rand() % MAX_RANGE; y = x + (rand() % (MAX_RANGE - x + 1)); z = 1 + rand() % MAX_RANGE; if (operation == 0) { z *= 1; } else { z *= -1; } cout << "left, right, value: " << x - 1 << ", " << y - 1 << ", " << z << endl; update_bruteforce(x, y, z, smallest, largest); update(x, y, z); test_show_data(); cout << "correct:\n"; cout << "\tsmallest = " << smallest << endl; cout << "\tlargest = " << largest << endl; cout << "possibly correct:\n"; cout << "\tsmallest = " << min_segment_tree[1] << endl; cout << "\tlargest = " << max_segment_tree[1] << endl; cout << "\n--------------------------------------------------------------\n"; cin.get(); } } } int main() { unit_test::test_brute_force_and_segment_tree(); } 

Answer 1

You need to separately store max / min for each interval, and what values ​​were added to it (just their sum). Here's how it might go wrong:

Suppose we are building a tree (here I will show only the min-tree) for the array [5, 1, 3, 7]. The tree is as follows:

  1 1 3 5 1 3 7 

Then add 1 to the entire interval. The tree is as follows:

  2 1 3 5 1 3 7 

because the distribution stopped at the first node, since the updated interval completely overlaps it.

Then add 1 to the range [0-1]. This range does not cover the entire interval of the first node, so we update the children, and then set min for the entire interval (that is, the value of the first node) as min of nodes 2 and 3. Here is the resulting tree:

  2 2 3 5 1 3 7 

And here is where he was mistaken - there is no element 2 in the array, but the tree claims that the minimum array of the entire array is 2. This is because the lower levels of the tree never get the information that their values ​​have been increased - the second node does not know about that its meanings are not [5, 1], but rather [6, 2].

To make it work correctly, you can add a third array that stores the values ​​that were added at all intervals - say, int added_to_interval[3 * MAX_RANGE + 1]; . Then, when you update the entire interval (in the case of i <= b && j >= e ), you also need to increase the added_to_interval[position] with value . In addition, when raising a tree to update nodes from the values ​​of child elements, you also need to add what was added to the entire interval (for example, max_segment_tree[position] = max(max_segment_tree[position * 2], max_segment_tree[position * 2 + 1]) + added_to_interval[position]; ).

EDIT:

The following are changes to the code to make it work:

 if (i <= b && j >= e) { max_segment_tree[position] += value; min_segment_tree[position] += value; added_to_interval[position] += value; return; } 

...

 update_tree(position * 2 , b , (b + e) / 2 , i, j, value); update_tree(position * 2 + 1 , (b + e) / 2 + 1 , e , i, j, value); max_segment_tree[position] = max(max_segment_tree[position * 2], max_segment_tree[position * 2 + 1]) + added_to_interval[position]; min_segment_tree[position] = min(min_segment_tree[position * 2], min_segment_tree[position * 2 + 1]) + added_to_interval[position]; 

I have not tested it extensively - I leave it to you, but I tried a bunch of examples that seemed to work correctly.

Also, I don't think you need 3 * MAX_RANGE + 1 elements in arrays - 2 * MAX_RANGE or something similar should be enough.

Answer 2

[b, e] is the range covered by * _ segment_tree [position] , and [i, j] is the current requested range.
About assortment storage:
* _ segment_tree [1] contains max / min of the entire data array. This is the root of the tree, because an array-based binary tree must be indexed from 1 . This is because the children of the n -th node of the tree are numbered 2 * n and 2 * n + 1 , and 0 cannot be used as n , because in this case 2 * n = n . Thus, if * _ segment_tree [k] contains min / max data [b, e] , then * segment_tree [2 * k] min / max data [b, (b + e) ​​/ 2] and * segment_tree is executed [2 * k + 1] - from the data [(b + e) ​​/ 2 + 1, e] - you can see these characters in the code.