懶惰的傳播

Created: November-22, 2018

比方說，你已經建立了一個分段樹。你需要更新陣列的值，這不僅會更改分段樹的葉節點，還會更改某些節點中的最小/最大值。讓我們看一個例子：

StackOverflow 文件

這是我們 8 個元素的最小分段樹。為了給你一個快速提醒，每個節點代表它們旁邊提到的範圍的最小值。讓我們說，我們想要將陣列的第一項的值增加 3 。我們怎麼能這樣做？我們將遵循我們進行 RMQ 的方式。該過程看起來像：

首先，我們遍歷根。 [0,0] 與 [0,7 ] 部分重疊，我們向兩個方向前進。
- 在左子樹， [0,0] 與 [0,3] 部分重疊，我們去兩個方向。
  - 在左子樹， [0,0] 與 [0,1] 部分重疊，我們去兩個方向。
    - 在左子樹， [0,0] 完全被交疊 [0,0] ，並且由於它的葉節點，我們通過增加由它 S 值更新節點 3 。並返回值 -1 + 3 = 2 。
    - 在右子樹， [1,1] 不與 [0,0] 重疊，我們返回節點（ 2 ）的值。
      這兩個返回的值的最小值（ 2 ， 2 ）是 2 ，所以我們更新了當前節點的值，並將其返回。
  - 在右子樹 [2,3] 不與 [0,0] 重疊時，我們返回節點的值。（ 1 ）。
    由於這兩個返回的值中的最小值（ 2 ， 1 ）是 1 ，我們更新當前節點的值並返回它。
- 在右子樹 [4,7] 不與 [0,0] 重疊時，我們返回節點的值。（ 1 ）。
最後更新根節點的值，因為兩個返回值 (1,1) 的最小值為 1 。

我們可以看到，更新單個節點需要時間複雜度，其中 n 是葉節點的數量。因此，如果我們被要求將一些節點從 i 更新為 j ，我們將需要時間複雜度。對於大的 n 值，這變得麻煩。讓我們*懶惰，*即只在需要時才工作。怎麼樣？當我們需要更新間隔時，我們將更新節點並將其子節點標記為需要更新並在需要時更新它。為此，我們需要一個陣列懶惰的相同尺寸段樹的。最初，惰性陣列的所有元素都是 0 表示沒有待定更新。如果 lazy [i]中存在非零元素，則此元素需要在進行任何查詢操作之前更新段樹中的節點 i 。我們該怎麼做？我們來看一個例子：

讓我們說，對於我們的示例樹，我們想要執行一些查詢。這些是：

將 [0,3] 增加 3 。
將 [0,3] 增加 1 。
遞增 [0,0] 由 2 。

增量[0,3]增加 3：

我們從根節點開始。首先，我們檢查這個值是否是最新的。為此我們檢查我們的惰性陣列是 0 ，這意味著該值是最新的。 [0,3] 部分重疊 [0,7] 。所以我們去了兩個方向。
- 在左子樹中，沒有待定更新。 [0,3] 完全重疊 [0,3] 。所以我們將節點的值更新為 3 。所以該值變為 -1 + 3 = 2 。這一次，我們不會一路走下去。我們不是向下，而是更新當前節點的延遲樹中的相應子節點，並將它們遞增 3 。我們還返回當前節點的值。
- 在右側子樹中，沒有待定更新。 [0,3] 不重疊 [4,7] 。所以我們返回當前節點 (1)的值。
  2 個返回值中的最小值（ 2 ， 1 ）是 1 。我們將根節點更新為 1 。

我們的細分樹和懶樹看起來像：

StackOverflow 文件

我們的 Lazy Tree 節點中的非零值表示，這些節點及其下方有待更新。如果需要，我們會更新它們。如果我們被問到，範圍 [0,3]中的最小值是多少，我們將來到根節點的左子樹，因為沒有掛起的更新，我們將返回 2 ，這是正確的。因此，此過程不會影響我們的分段樹演算法的正確性。

將[0,3]增加 1：

我們從根節點開始。沒有待定更新。 [0,3] 部分重疊 [0,7] 。所以我們去兩個方向。
- 在左子樹中，沒有待定更新。 [0,3] 完全重疊 [0,3] 。我們更新當前節點： 2 + 1 = 3 。由於這是一個內部節點，我們將其在 Lazy Tree 中的子節點更新為 1 。我們還將返回當前節點（ 3 ）的值。
- 在右側子樹中，沒有待定更新。 [0,3] 不重疊 [4,7] 。我們返回當前節點（ 1 ）的值。
我們通過取最少兩個返回的值（更新的根節點 3 ， 1 ）。

我們的細分樹和懶樹將如下所示：

StackOverflow 文件

正如你所看到的，我們正在 Lazy Tree 上積累更新但不會將其推遲。這就是 Lazy Propagation 的意思。如果我們沒有使用它，我們不得不將值推到葉子上，這將花費我們更多不必要的時間複雜性。

將[0,0]增加 2：

我們從根節點開始。由於 root 是最新的， [0,0] 部分重疊 [0,7] ，我們會向兩個方向前進。
- 在左子樹，當前節點是最新的， [0,0] 部分重疊 [0,3] ，我們去兩個方向。
  - 在左子樹中，Lazy Tree 中的當前節點具有非零值。因此，有一個尚未傳播到此節點的更新。我們將首先在 Segment Tree 中更新此節點。所以這變成了 -1 + 4 = 3 。然後我們將把這個 4 傳播給懶樹中的孩子們。由於我們已經更新了當前節點，因此我們將 Lazy Tree 中當前節點的值更改為 0 。然後 [0,0] 部分重疊 [0,1] ，所以我們去兩個方向。
    - 在左側節點，由於 Lazy Tree 的當前節點中存在非零值，因此需要更新該值。所以我們將值更新為 -1 + 4 = 3 。現在，由於 [0,0] 完全重疊 [0,0] ，我們將當前節點的值更新為 3 + 2 = 5 。這是一個葉子節點，因此我們不再需要傳播該值。我們將 Lazy Tree 中的相應節點更新為 **0，**因為所有值都已傳播到此節點。我們返回當前節點（ 5 ）的值。
    - 在右側節點，需要更新值。所以該值變為： 4 + 2 = 6 。由於 [0,0] 不重疊 [1,1] ，我們返回當前節點（ 6 ）的值。我們還將 Lazy Tree 中的值更新為 0 。不需要傳播，因為這是葉節點。
      我們更新使用最少兩個返回的值（當前節點 5 ， 6 ）。我們返回當前節點（ 5 ）的值。
  - 在右側子樹中，有一個待定更新。我們將節點的值更新為 1 + 4 = 5 。由於這不是葉節點，我們將值傳播到我們的 Lazy Tree 中的子節點，並將當前節點更新為 0 。由於 [0,0] 不與 [2,3] 重疊，因此我們返回當前節點（ 5 ）的值。
    我們使用最小的返回值（更新當前節點 5 ， 5 ）和返回值（ 5 ）。
- 在右子樹中，沒有待定更新，並且由於 [0,0] 不重疊 [4,7] ，我們返回當前節點（ 1 ）的值。
我們更新使用最小兩個返回的值（的根節點 5 ， 1 ）。

我們的細分樹和懶樹將如下所示：

StackOverflow 文件

我們可以注意到， [0,0] 處的值在需要時獲得了所有增量。

現在，如果要求你找到範圍 [3,5]中的最小值，如果你已經理解了這一點，則可以輕鬆地確定查詢的結果，返回值將為 1 。我們的細分樹和懶樹看起來像：

StackOverflow 文件

我們只是遵循我們在查詢 RMQ 時所遵循的相同過程，其中新增了檢查 Lazy Tree 以進行掛起更新的約束。

我們可以做的另一件事是不是從每個節點返回值，因為我們知道當前節點的子節點是什麼，我們可以簡單地檢查它們以找到這兩個節點中的最小值。

用於在 Lazy Propagation 中更新的虛擬碼將是：

Procedure UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
                                endRange, delta, low, high, position):
if low > high                                                //out of bounds
    Return
end if
if LazyTree[position] is not equal to 0                      //update needed
    segmentTree[position] := segmentTree[position] + LazyTree[position]
    if low is not equal to high                              //non-leaf node    
        LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + delta
        LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + delta
    end if
    LazyTree[position] := 0
end if
if startRange > low or endRange < high                       //doesn't overlap
    Return
end if
if startRange <= low && endRange >= high                     //total overlap
    segmentTree[position] := segmentTree[position] + delta
    if low is not equal to high
        LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + delta
        LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + delta
    end if
    Return
end if
//if we reach this portion, this means there's a partial overlap
mid := (low + high) / 2
UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
                                endRange, delta, low, mid, 2 * position + 1)
UpdateSegmentTreeLazy(segmentTree, LazyTree, startRange,
                                endRange, delta, mid + 1, high, 2 * position + 2)
segmentTree[position] := min(segmentTree[2 * position + 1], 
                                                    segmentTree[2 * position + 2])

而 Lazy Propagation 中 RMQ 的虛擬碼將是：

Procedure RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh, low, high, position):
if low > high
    Return infinity
end if
if LazyTree[position] is not equal to 0                      //update needed
    segmentTree[position] := segmentTree[position] + LazyTree[position]
    if low is not equal to high
        segmentTree[position] := segmentTree[position] + LazyTree[position]
    if low is not equal to high                              //non-leaf node    
        LazyTree[2 * position + 1] := LazyTree[2 * position + 1] + LazyTree[position]
        LazyTree[2 * position + 2] := LazyTree[2 * position + 2] + LazyTree[position]
    end if
    LazyTree[position] := 0
end if
if qLow > high and qHigh < low                                //no overlap
    Return infinity
end if
if qLow <= low and qHigh >= high                              //total overlap
    Return segmentTree[position]
end if
//if we reach this portion, this means there's a partial overlap
mid := (low + high) / 2
Return min(RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh, 
                                        low, mid, 2 * position + 1),
           RangeMinimumQueryLazy(segmentTree, LazyTree, qLow, qHigh,
                                        mid + 1, high, 2 * position + 1)