懒惰的传播

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)