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

Question

我正在从一个数据数组中实现线段树，我还想在更新一系列数据时保持树的最大/最小值。这是我遵循本教程的初步方法 http://p--np.blogspot.com/2011/07/segment-tree.html .不幸的是它根本不起作用，逻辑对我来说很有意义，但我对 b 和 e 有点困惑，我想知道这是数据数组？或者它是树的实际范围？据我了解，max_segment_tree[1] 应该包含 [1, MAX_RANGE] 范围内的 max 而 min_segment_tree[1 ] 应该包含范围 [1, MAX_RANGE] 的 min。

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

因为更新间隔完全覆盖第一个节点后，传播已停止。

然后在 [0-1] 范围内加 1。这个范围没有覆盖第一个节点的整个区间，所以我们更新 child ，然后将整个区间的最小值(即第一个节点的值)设置为节点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 或类似的元素就足够了。