段树中的数据映射和延迟传播

Question

看起来在整个互联网上的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]的读状态.

我在这里面对这个问题.我的分段树实现使得每个节点的值是其左右子节点的总和.因此,当我更新节点的值时,我要更新它的所有父节点.为了解决逻辑问题,现在我正在更新节点的所有父节点(直到它到达树的根).但这会带来性能损失,我使用分段树进行快速批量更新的整个目的正在被杀死.

任何人都可以解释一下,我在使用分段树时出错了吗？

Answer 1

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

访问查询节点时，您将遍历从根到查询节点的路径，同时处理所有待处理的更新。由于您需要访问 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);
    }
};