14

看起来整个互联网上只有一篇关于 Segment Tree 中延迟传播的好文章，它是： 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]的读取状态。

在这里，我面临这个问题。我的段树实现是这样的，每个节点的值是其左右子节点的总和。因此，当我更新节点的值时，我必须更新它的所有父节点。为了解决逻辑问题，现在我正在更新节点的所有父节点（直到它到达树的根）。但这会对性能造成影响，我使用分段树进行快速批量更新的整个目的都被扼杀了。

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

4

2 回答 2

3

我将惰性更新操作与正常更新操作进行对比，以及这如何改变查询操作。

在正常的单个更新操作中，您更新树的根，然后递归地仅更新树的所需部分（从而为您提供O(log(n))速度）。如果您尝试对范围更新使用相同的逻辑，您可以看到它如何恶化O(n)（考虑非常广泛的范围，并看到您主要需要更新树的两个部分）。

因此，为了克服这个O(n)想法，只有在您真正需要时才更新树（查询/更新先前更新的段，从而使您的更新变得懒惰）。所以这是它的工作原理：

  • 树的创建完全一样。唯一的细微差别是您还创建了一个数组，其中包含有关潜在更新的信息。
  • 当您更新树的节点时，您还检查它是否需要更新（来自先前的更新操作），如果是 - 您更新它，标记孩子将来要更新并取消标记节点（懒惰）
  • 当您查询树时，您还会检查节点是否需要更新，如果需要更新它，请将其标记为子节点，然后再取消标记。

下面是一个更新和查询的例子（解决最大范围查询）。如需完整代码，请查看本文。

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-20T01:30:15.737 回答
2

当您查询段树中的节点时，您需要确保其所有祖先以及节点本身都已正确更新。您在访问查询节点时执行此操作。

在访问查询节点时，您会遍历从根到查询节点的路径，同时处理所有待处理的更新。由于您需要访问 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);
    }
};
于 2012-07-10T13:48:42.367 回答