數據映射和懶惰傳播

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] 
..................................... 

首先查詢，如果我更新[0 4]，其數據將被改變，並且其子將被標記。 第二個查詢，是段的讀取狀態[0 9]。

在這裏，我面臨的問題。我的分段樹實現是這樣的，每個節點的值是其左側和右側子節點的總和。所以當我更新節點的價值時，我必須更新它的所有父母。 爲了解決邏輯問題，現在我正在更新節點的所有父節點（直到到達樹的根節點）。 但是，這是採取性能收費和我的整個使用段樹快速批量更新的目的被殺害。

任何人都可以請解釋一下，我在使用分段樹時會出錯嗎？

Answer 1

當您查詢分段樹中的節點時，需要確保其所有祖先和節點本身都已正確更新。您在訪問查詢節點時執行此操作。

在訪問查詢節點時，您會遍歷從根節點到查詢節點的路徑，同時處理所有掛起的更新。由於您需要訪問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); 
    } 
}; 

Answer 2

我會將延遲更新操作與正常更新操作進行對比，以及如何更改查詢操作。

在正常的單個更新操作中，您更新樹的根，然後遞歸地僅更新樹的所需部分（從而爲您提供O(log(n))速度）。如果您嘗試使用相同的邏輯來進行範圍更新，您可以看到它會如何惡化到O(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)); 
}