4

データの配列からセグメント ツリーを実装しています。また、データの範囲を更新しながら、ツリーの最大/最小を維持したいと考えています。これは、このチュートリアル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]);
}

EDIT テストケースの追加:

#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();
}
4

2 に答える 2

6

各間隔の最大/最小、およびそれに追加された値 (それらの合計のみ) を個別に保存する必要があります。それがどのようにうまくいかないかは次のとおりです。

配列 [5, 1, 3, 7] のツリーを作成するとします (ここでは最小ツリーのみを示します)。ツリーは次のようになります。

   1
 1   3
5 1 3 7

次に、間隔全体に 1 を追加します。ツリーは次のようになります。

   2
 1   3
5 1 3 7

更新された間隔が最初のノードを完全にカバーするため、伝播が最初のノードで停止したためです。

次に、範囲 [0-1] に 1 を追加します。この範囲は最初のノードの間隔全体をカバーしていないため、子を更新し、間隔全体の最小値 (つまり、最初のノードの値) をノード 2 と 3 の最小値に設定します。結果のツリーです：

   2
 2   3
5 1 3 7

そして、ここが間違っているところです - 配列には要素 2 はありませんが、ツリーは配列全体の最小値が 2 であると主張しています。増加しました - 2 番目のノードは、その値が [5, 1] ではなく [6, 2] であるという事実を認識していません。

正しく機能させるために、間隔全体に追加された値を保持する 3 番目の配列を追加できます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 またはそのようなもので十分です。

于 2012-08-05T09:11:37.443 に答える
3

[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]の最小/最大を保持する場合、*segment_tree[ 2*k ]は、データ [ b, ( b + e ) / 2 ]の最小/最大値と*segment_tree[ 2*k + 1 ] -データ [ ( b + e ) / 2 + 1, e ]の最小値/最大値を保持します。 - これらの指標はコードで確認できます。

于 2012-08-05T07:24:30.320 に答える