algorithm - 线段树中的数据映射和惰性传播

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]，它的数据将被更改并且它的 child 将被标记。第二个查询，是段 [0 9] 的读取状态。

这里我遇到了问题。我的线段树实现是这样的，即每个节点的值是其左右子节点的总和。所以当我更新节点的值时，我必须更新它的所有父节点。为了解决逻辑问题，现在我正在更新节点的所有父节点(直到它到达树的根)。但这正在影响性能，我使用线段树进行快速批量更新的整个目的都被扼杀了。

谁能解释一下，我在使用线段树时哪里出错了？

Answer 1

我将对比惰性更新操作与普通更新操作，以及这如何改变查询操作。

在正常的单个更新操作中，您更新树的根，然后递归地只更新树的所需部分(因此给您一个 O(log(n)) 速度)。如果您尝试对范围更新使用相同的逻辑，您会看到它如何恶化到 O(n)(考虑非常广泛的范围，您将主要需要更新的两个部分树)。

所以为了克服这个O(n) 的想法是只在你真正需要它的时候更新树(查询/更新之前更新过的段，从而使你的更新变得懒惰) .所以这是它的工作原理:

• 树的创建完全相同。唯一的细微差别是您还创建了一个数组来保存有关潜在更新的信息。
• 当你更新树的节点时，你还检查它是否需要更新(从之前的更新操作)，如果是 - 你更新它，标记 child 将来要更新并取消标记节点(懒惰)
• 当您查询树时，您还检查节点是否需要更新，如果需要更新，标记它的子节点，然后取消标记。

这里是一个更新查询的例子(求解最大范围查询)。对于 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));
}