如何在保持最大值和最小值的同时更新段树中的范围？

Question

我正在从一组数据中实现段树,我还想在更新数据范围时保持树的最大/最小值.这是我在本教程http://p--np.blogspot.com/2011/07/segment-tree.html之后的初始方法.遗憾的是它并没有在所有的工作中,逻辑对我来说很有意义,但我有点困惑b和e,我不知道这是范围data阵列？或者它是树的实际范围？根据我的理解,max_segment_tree[1]应该保持max范围,[1, MAX_RANGE]同时min_segment_tree[1]应该保持min范围[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]);
}

编辑 添加测试用例:

#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

您需要单独存储每个间隔的最大值/最小值,以及添加了哪些值(只是它们的总和).这是它可能出错的方式:

假设我们正在为数组[5,1,3,7]构建一个树(我只在这里显示最小树).树看起来像这样:

   1
 1   3
5 1 3 7

然后我们在整个区间加1.树看起来像这样:

   2
 1   3
5 1 3 7

因为传播已在第一个节点上停止,因为更新的间隔完全覆盖了它.

然后将1添加到范围[0-1].此范围不包括第一个节点的整个间隔,因此我们更新子节点,然后将整个间隔的min(即第一个节点的值)设置为节点2和3的min.是结果树:

   2
 2   3
5 1 3 7

这是错误的地方 - 数组中没有元素2,但树声称整个数组的最小值为2.这种情况正在发生,因为树的较低级别实际上从未获得其值具有的信息增加了 - 第二个节点没有意识到它的值不是[5,1]而是[6,2].

为了使其正常工作,您可以添加第三个数组,以保留已添加到整个时间间隔的值 - 例如,int added_to_interval[3 * MAX_RANGE + 1];.然后,当你更新整个区间(的情况下i <= b && j >= e),你还必须增加added_to_interval[position]与value.此外,当上升树以从子项的值更新节点时,您还必须添加已添加到整个时间间隔(例如max_segment_tree[position] = max(max_segment_tree[position * 2], max_segment_tree[position * 2 + 1]) + added_to_interval[position];).

编辑:

以下是使其工作的代码更改:

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];

我没有对它进行过广泛的测试 - 我将它留给你,但我尝试了一些似乎正常工作的例子.

另外,我认为你不需要3*MAX_RANGE + 1个数组元素 - 2*MAX_RANGE或类似的东西就足够了.