分段樹中的懶惰傳播？

那麼，我正試圖解決Codechef上的這個Flipping coins問題。我正在用細分樹來解決它。但獲得時間限制超過。我搜索並發現我必須使用惰性傳播。但我無法理解。我的更新函數遞歸地工作（從上到下）。請給出一些提示或用示例來解釋它。同時指出我必須更改代碼的地方。分段樹中的懶惰傳播？

在更新期間翻轉硬幣，如果節點值是1個它變化爲0，如果它是0，則變化爲1。

的開始和結束是原始陣列的限制。樹是分段樹數組。

void update(int node, int start, int end,int pos)//pos=position to update 
{ 
    if(start==end) tree[node]=(tree[node]==0) ? 1 : 0; 
    else 
    { 
     int mid=(start+end)/2; 
     if(mid>=pos) update(2*node + 1, start, mid, pos); 
     else update(2*node + 2, mid+1, end, pos); 

     tree[node]=tree[2*node +1] + tree[2*node +2]; 
    } 
}

來源

2012-05-23 dejavu

要將5..15標記爲「是」，以下是您所需要的。操作中只涉及7個節點，遠小於不使用惰性傳播的情況。可以證明最多可能涉及2logn - 1節點，其中n是該範圍。

  0..31u 
     / \ 
     0..15u 16..31n 
    / \ 
    0..8u 9..15y 
/ \ 
0..4n 5..8y 

(u: unknown, look deeper; y: yes; n: no)

沒有惰性傳播，段樹並不比普通數組好。

有關如何實現的更多細節由您決定。你應該自己解決。

來源

2012-05-24 08:40:44 Haozhun

延遲傳播意味着僅在需要時更新。其技術允許範圍更新以漸近時間複雜度O（logN）（N這裏是範圍）進行。假設你想更新範圍[0,15]，然後你更新節點[0,15]，並在節點中設置一個標誌，表示它的子節點將被更新。（使用標記值情況下該標誌未被使用）。

可能的壓力測試案例：

0 1 10萬

0 1 10萬 ......重複Q倍（其中Q = 99999）並且第100000個查詢將是

在這種情況下，大多數實現會坐在翻轉100000個硬幣99999次，只是爲了回答一個簡單的查詢在結束和超時。

通過惰性傳播，您只需要翻轉節點[0,100000] 99999次並設置/取消設置其子節點更新的標誌。當詢問實際查詢本身時，您開始遍歷其子項並開始翻轉它們，向下推該標誌並取消設置父項的標誌。

哦，並確保你正在使用適當的I/O例程（scanf和printf，而不是cin和cout，如果它的C++）希望這給你一個懶惰傳播意味着什麼的想法。更多信息： http://www.spoj.pl/forum/viewtopic.php?f=27&t=8296

來源

2012-05-24 10:05:43 csprajeeth

當你說「說你要更新的範圍[0,15]，那麼你更新的節點[0,15]，並在節點設置一個標誌那就是說它的子節點是要更新的「如何更新[0,15]而不更新子節點。我沒有得到這個概念。這就是爲什麼我在這裏問。也可以使用自頂向下的遞歸函數來完成嗎？在update_tree函數中的 – dejavu

我會對比懶更新操作正常更新操作以及如何改變查詢操作。

在正常的單個更新操作中，您更新樹的根，然後遞歸地僅更新樹的所需部分（從而爲您提供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)); 
}

來源

2015-01-20 01:29:14

不會標記不在範圍內的節點爲懶惰？因爲在超出範圍之前檢查 –

，所以你要做一個懶惰的檢查，不好意思的是檢查它是否標記爲懶惰。我的錯 –

分段樹中的懶惰傳播？

回答

相關問題