14

インターネット全体のセグメントツリーでの遅延伝播に関する優れた記事は1つしかないようです。それは、 http ：//www.spoj.pl/forum/viewtopic.php？f = 27＆t=8296です。

クエリノードのみを更新し、その子をマークするという概念を理解しました。しかし、私の質問は、最初に子ノードを照会し、後で親ノードを照会するとどうなるかということです。

このツリー内（ヒープの配列内の場所とともに）

           0->[0 9]
      1->[0 4]    2->[5 9]
   3->[0 2] 4->[3 4]  5->[5 7] 6->[8 9]
 .....................................

最初のクエリ、[0 4]を更新すると、そのデータが変更され、その子にフラグが付けられます。2番目のクエリは、セグメント[09]の読み取り状態です。

ここで私は問題に直面します。私のセグメントツリーの実装では、各ノードの値はその左と右の子の合計になります。したがって、ノードの値を更新するときは、すべての親を更新する必要があります。論理的な問題を修正するために、ノードのすべての親を更新しています（ツリーのルートに到達するまで）。しかし、これはパフォーマンスを低下させており、高速バッチ更新にセグメントツリーを使用するという私の目的全体が失われています。

セグメントツリーの使用でどこが間違っているのか、誰か説明してもらえますか？

4

2 に答える 2

3

遅延更新操作と通常の更新操作を対比し、これがクエリ操作をどのように変更するかを説明します。

通常の単一の更新操作では、ツリーのルートを更新してから、ツリーの必要な部分のみを再帰的に更新します (したがってO(log(n))速度が向上します)。範囲の更新に同じロジックを使用しようとすると、どのように悪化するかがわかりますO(n)(非常に広い範囲を考慮して、ツリーの両方の部分を更新する必要があることがほとんどです)。

したがって、この考えを克服するにO(n)は、本当に必要な場合にのみツリーを更新することです (以前に更新されたセグメントに対してクエリ/更新を行い、更新を遅延させます)。したがって、これがどのように機能するかです：

  • ツリーの作成はまったく同じままです。唯一の小さな違いは、潜在的な更新に関する情報を保持する配列も作成することです。
  • ツリーのノードを更新するときは、(前回の更新操作から) 更新する必要があるかどうかも確認し、更新する必要がある場合は、更新し、子を将来更新するようにマークし、ノードのマークを解除します (遅延)。
  • ツリーをクエリするときは、ノードを更新する必要があるかどうかも確認し、更新する必要がある場合は、それを子としてマークし、後でマークを解除します。

更新とクエリの例を次に示します (最大範囲クエリの解決)。完全なコードについては、この記事を確認してください。

void update_tree(int node, int a, int b, int i, int j, int value) {
    if(lazy[node] != 0) { // This node needs to be updated
        tree[node] += lazy[node]; // Update it
        if(a != b) {
            lazy[node*2] += lazy[node]; // Mark child as lazy
            lazy[node*2+1] += lazy[node]; // Mark child as lazy
        }
        lazy[node] = 0; // Reset it
    }

    if(a > b || a > j || b < i) // Current segment is not within range [i, j]
        return;

    if(a >= i && b <= j) { // Segment is fully within range
        tree[node] += value;
        if(a != b) { // Not leaf node
            lazy[node*2] += value;
            lazy[node*2+1] += value;
        }
        return;
    }

    update_tree(node*2, a, (a+b)/2, i, j, value); // Updating left child
    update_tree(1+node*2, 1+(a+b)/2, b, i, j, value); // Updating right child
    tree[node] = max(tree[node*2], tree[node*2+1]); // Updating root with max value
}

およびクエリ:

int query_tree(int node, int a, int b, int i, int j) {
    if(a > b || a > j || b < i) return -inf; // Out of range

    if(lazy[node] != 0) { // This node needs to be updated
        tree[node] += lazy[node]; // Update it
        if(a != b) {
            lazy[node*2] += lazy[node]; // Mark child as lazy
            lazy[node*2+1] += lazy[node]; // Mark child as lazy
        }
        lazy[node] = 0; // Reset it
    }

    if(a >= i && b <= j) // Current segment is totally within range [i, j]
        return tree[node];

    return max(query_tree(node*2, a, (a+b)/2, i, j), query_tree(1+node*2, 1+(a+b)/2, b, i, j));
}
于 2015-01-20T01:30:15.737 に答える
2

セグメント ツリー内のノードをクエリするときは、そのすべての祖先とノード自体が適切に更新されていることを確認する必要があります。これは、クエリ ノードにアクセスしているときに行います。

クエリ ノードにアクセスしている間、保留中のすべての更新を処理しながら、ルートからクエリ ノードまでのパスをたどります。O(log N) 個の祖先にアクセスする必要があるため、特定のクエリ ノードに対して、O(log N) 個の作業のみを行います。

遅延伝播を使用したセグメント ツリーのコードを次に示します。

// interval updates, interval queries (lazy propagation)  
const int SN = 256;  // must be a power of 2

struct SegmentTree {

    // T[x] is the (properly updated) sum of indices represented by node x
    // U[x] is pending increment for _each_ node in the subtree rooted at x 
    int T[2*SN], U[2*SN];

    SegmentTree() { clear(T,0), clear(U,0); }

    // increment every index in [ia,ib) by incr 
    // the current node is x which represents the interval [a,b)
    void update(int incr, int ia, int ib, int x = 1, int a = 0, int b = SN) { // [a,b)
        ia = max(ia,a), ib = min(ib,b); // intersect [ia,ib) with [a,b)
        if(ia >= ib) return;            // [ia,ib) is empty 
        if(ia == a && ib == b) {        // We push the increment to 'pending increments'
            U[x] += incr;               // And stop recursing
            return; 
        }
        T[x] += incr * (ib - ia);          // Update the current node
        update(incr,ia,ib,2*x,a,(a+b)/2);  // And push the increment to its children
        update(incr,ia,ib,2*x+1,(a+b)/2, b);
    }

    int query(int ia, int ib, int x = 1, int a = 0, int b = SN) {
        ia = max(ia,a), ib = min(ib,b); //  intersect [ia,ib) with [a,b)
        if(ia >= ib) return 0;          // [ia,ib) is empty 
        if(ia == a && ib == b) 
            return U[x]*(b - a) + T[x];

        T[x] += (b - a) * U[x];           // Carry out the pending increments
        U[2*x] += U[x], U[2*x+1] += U[x]; // Push to the childrens' 'pending increments'
        U[x] = 0;

        return query(ia,ib,2*x,a,(a+b)/2) + query(ia,ib,2*x+1,(a+b)/2,b);
    }
};
于 2012-07-10T13:48:42.367 に答える