段树中的延迟传播？

Question

好吧,我试图在Codechef上解决这个翻转硬币问题.用分段树解决它.但是时间限制超过了.我搜索并发现我必须使用懒惰传播.但我无法理解.我的更新功能递归地工作(从上到下).请提供一些提示或用例子解释.还要指出我必须更改代码的位置.

在翻转硬币时,如果节点值为1,则在更新期间将其更改为0,如果为0,则将其更改为1.

start和end是原始数组的限制.树是分段树阵列.

void update(int node, int start, int end,int pos)//pos=position to update
{
    if(start==end) tree[node]=(tree[node]==0) ? 1 : 0;
    else
    {
        int mid=(start+end)/2;
        if(mid>=pos) update(2*node + 1, start, mid, pos);
        else update(2*node + 2, mid+1, end, pos);

        tree[node]=tree[2*node +1] + tree[2*node +2];
    }
}

Answer 1

延迟传播仅在需要时进行更新.它是一种允许以渐近时间复杂度O(logN)执行范围更新的技术(这里N是范围).

假设您要更新范围[0,15],然后更新节点[0,15]并在节点中设置一个标志,表示要更新子节点(如果标志不是则使用标记值用过).

可能的压力测试案例:

0 1 100000

0 1 100000

0 1 100000 ...重复Q次(其中Q = 99999)和第100000次查询

1 1 100000

在这种情况下,大多数实施人员只会翻转100000个硬币99999次,以便最终回答一个简单的查询并超时.

使用延迟传播,您只需要翻转节点[0,100000] 99999次并设置/取消设置其子项将被更新的标志.当询问实际查询本身时,您开始遍历其子项并开始翻转它们,按下该标志并取消设置父标志.

哦,并确保你正在使用正确的I/O例程(scanf和printf而不是cin和cout,如果它的c ++)希望这能让你了解延迟传播的含义.更多信息:http: //www.spoj.pl/forum/viewtopic.php？f = 27&t = 8296