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

Question

I'm implementing segment tree from an array of data, and I also want to maintaining the max/min of the tree while updating a range of data. Here is my initial approach following this tutorial http://p--np.blogspot.com/2011/07/segment-tree.html. Unfortunately it doesn't work at all, the logic makes sense to me, but I'm a little confused about b and e, I wonder is this the range of the data array? or it's the actual range of the tree? From what I understand, the max_segment_tree[1] should hold the max of the range [1, MAX_RANGE] while min_segment_tree[1] should hold the min of the 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();
}      

Fcc

How exactly does it fail - wrong values, runtime errors? Do you have a query function? Also, the operation you're trying to support is "add a value to all the numbers in a range" and then answer queries for min/max in a range, right? – Legendre

@IvanVergiliev: It gave me wrong answer, and yes, I want to update all values within a range [left, right] but still maintains the max/min of the tree. It's not necessary to query a range [left, right] because I only want to look at either max/min. Thanks. – Fcc

Just a small note about your unit tests (which you may already aware of, but still): automated tests are usually better than those that require human interaction. So, instead of manually comparing the results and pressing a key, I would use an assert or something similar so that they keep running while they are correct, and break as soon as something goes wrong. Also, rand() % 1 is always zero, you probably want rand() & 1 or rand() % 2 – Legendre

@IvanVergiliev: Thanks. I often do assert after seeing several correct test cases. Before that, I find console output easier to visualize and track my bugs. rand() % 1 is really my bad :(. The consequence of coding late at night. – Fcc

Answer 1

You need to store separately the max/min for each interval, AND what values have been added to it (just their sum). Here's how it could go wrong:

Suppose we're building a tree (I'll only show the min tree here) for the array [5, 1, 3, 7]. The tree looks like this:

   1
 1   3
5 1 3 7

Then we add 1 to the whole interval. The tree looks like this:

   2
 1   3
5 1 3 7

because the propagation has stopped on the first node since the updated interval covers it completely.

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

   2
 2   3
5 1 3 7

And here is where it got wrong - there is no element 2 in the array, yet the tree claims that the min of the whole array is 2. This is happening because the lower levels of the tree never actually get the information that their values have been increased - the second node isn't aware of the fact that its values are not [5, 1] but rather [6, 2].

In order to make it work correctly, you can add a third array that keeps the values that have been added to whole intervals - say, int added_to_interval[3 * MAX_RANGE + 1];. Then, when you're updating a whole interval (the case where i <= b && j >= e), you also have to increment added_to_interval[position] with value. Also, when going up the tree to update the nodes from the values of the children, you also have to add that has been added to the whole interval (e.g. max_segment_tree[position] = max(max_segment_tree[position * 2], max_segment_tree[position * 2 + 1]) + added_to_interval[position];).

EDIT:

Here are the changes to the code to make it working:

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 haven't tested it extensively - I'm leaving that 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 the arrays - 2 * MAX_RANGE or something like that should be enough.

Legendre

Thanks a lot! I will try it out and let you know. By the way, if we propagate down to each child, will the time still be O(logN)? – Fcc

No, if you propagate down to each child, the performance gets worse than using an array, because for a range of length l, you'd have to visit about 2*l nodes, whereas with an array you can just visit all the values in the range. – Legendre

Ah, got it. Sorry for asking a very stupid question. How could it be worse when using divide-conquer. By the way, I ran a quick test for 1000 records, and the result is as expected for maximum but fail on the minimum, it's quite strange. – Fcc

If you can find a small enough test case, I could look into it - or you could practice your debugging skills. – Legendre

Answer 2

[b, e] is the range, covered by *_segment_tree[ position ], and [i, j] is the current queried range.
About range storage:
*_segment_tree[ 1 ] holds max/min of the whole data array - It's the root of the tree, because array-based binary tree has to be indexed from 1. It's because children of n-th node of the tree are numbered 2*n and 2*n + 1, and 0 cannot be used as n, because in that case 2*n = n. Hereby, if *_segment_tree[k] holds min/max of data[b, e], then *segment_tree[ 2*k ] holds min/max of data[ b, ( b + e ) / 2 ] and *segment_tree[ 2*k + 1 ] - of data[ ( b + e ) / 2 + 1, e ] - you can see these indicies in the code.

Taluk

Answer 3

The segment tree can be generically implemented by two types one is through DMA and other is through standard vector method especially this is a template code for those people who do Competitive programming

class __SEGMENTTREES
{
private:
public:


    void __SegTreeCreation(int Ind, int Left, int Right, vector<int> &v, vector<int> &Seg)
    {
        if (Left == Right)
        {
            Seg[Ind] = v[Left];
            return;
        }
        else
        {
            int Mid = Left + (Right - Left) / 2;
            __SegTreeCreation(2 * Ind + 1, Left, Mid, v, Seg);
            __SegTreeCreation(2 * Ind + 2, Mid + 1, Right, v, Seg);
            Seg[Ind] = min(Seg[2 * Ind + 1], Seg[2 * Ind + 2]);
        }
    }


    void __UpdateSegTree(int Ind, int Left, int Right, int Loc, int Newval, vector<int> &Seg)
    {
        int Mid = Left + (Right - Left) / 2;
        if ((Left == Right) && (Left == Loc))
            Seg[Ind] = Newval;
        if (Mid >= Loc)
            __UpdateSegTree(Ind * 2 + 1, Left, Mid, Loc, Newval, Seg), Seg[Ind] = min(Seg[2 * Ind + 1], Seg[2 * Ind + 2]);
        else
            __UpdateSegTree(Ind * 2 + 2, Mid + 1, Right, Loc, Newval, Seg), Seg[Ind] = min(Seg[2 * Ind + 1], Seg[2 * Ind + 2]);
    }


    int __SegTreeQuery(int Ind, int Left, int Right, int TreeLeft, int TreeRight, vector<int> &Seg)
    {
        if (Left > TreeRight || Right < TreeLeft)
            return INT_MAX;
        else if (TreeLeft >= Left && TreeRight <= Right)
            return Seg[Ind];
        else
        {
            int Mid = TreeLeft + (TreeRight - TreeLeft) / 2;
            return (min(__SegTreeQuery(2 * Ind + 1, Left, Right, TreeLeft, Mid, Seg), __SegTreeQuery(2 * Ind + 2, Left, Right, Mid + 1, TreeRight, Seg)));
        }
    }
};

This is the basic Code of segment tree creation , updating the value and Queries.

Ratoon