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

Question

我正在从一组数据中实现分段树，并且我还想在更新一系列数据时保持树的最大/最小值。这是我遵循本教程http://p--np.blogspot.com/2011/07/segment-tree.html的初步方法。不幸的是，它根本不起作用，逻辑对我来说很有意义，但我对band有点困惑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]。这个范围并没有覆盖第一个节点的整个区间，所以我们更新孩子，然后将整个区间的最小值（即第一个节点的值）设置为节点2和3的最小值。这里是结果树：

   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 或类似的东西就足够了。

Answer 2

[b, e]是范围，被*_segment_tree[ position ]覆盖，[i, j]是当前查询的范围。
关于范围存储：
*_segment_tree[ 1 ]保存整个数据数组的最大值/最小值- 它是树的根，因为基于数组的二叉树必须从1开始索引。这是因为树的第n个节点的子节点编号为2*n和2*n + 1，并且0不能用作n，因为在这种情况下2*n = n。因此，如果*_segment_tree[k]持有data[b, e]的 min/max ，则*segment_tree[ 2*k ]保存数据[ b, ( b + e ) / 2 ]的最小/最大值和*segment_tree[ 2*k + 1 ] -数据[ ( b + e ) / 2 + 1, e ] - 您可以在代码中看到这些指标。