セグメントツリー内のデータのマッピングと怠惰な伝播

Question

がセグメントツリーの怠惰な伝播の唯一の良い記事が全体のインターネット上にあり、それは次のようになります。 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] 
..................................... 

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

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

誰でも説明してください。セグメントツリーの使用に間違いがありますか？

Answer 1

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

クエリノードにアクセスしている間は、保留中のすべての更新を処理しながら、ルートからクエリノードへのパスをトラバースします。あなたが訪問する必要があるO（log N）祖先があるので、任意の与えられたクエリノードに対して、あなたはO（ログ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); 
    } 
}; 

Answer 2

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

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

これを克服するには、本当に必要なときにのみツリーを更新するというアイデアがあります（これは以前に更新されたセグメントでクエリ/更新され、更新が怠惰になります）。だからそれはどのように動作しますか：

• ツリーの作成はまったく同じにとどまります。唯一の小さな違いは、潜在的な更新に関する情報を保持する配列を作成することです。
• ツリーのノードを更新するときに、更新する必要があるかどうか（前回の更新操作から）をチェックし、更新する場合は、将来更新する子をマークしてノードをマーク解除します
• ）ツリーを照会するときに、ノードを更新する必要があるかどうかをチェックし、更新する場合は、そのノードをマークし、後でマークを解除します。

ここでは、更新とクエリ（最大範囲クエリの解決）の例を示します。 full code - check this articleの場合。

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)); 
}