data-structures - 分段树，延迟传播

Question

我对这个结构如何工作以及如何更新它有一个很好的想法，但是当涉及到延迟传播时我不知道该怎么做，因为很多很多问题都需要在比赛中通过我想知道如何让它工作。

我在 spoj 上尝试这个问题：http ://www.spoj.com/problems/CDC12_H/

如果有人可以向我解释惰性传播如何适应这种情况，我会接受并研究这个想法，我真的不想发布我的代码，因为我的想法是让我自己完成这项工作，但是帮助不大。

我希望有人能解决我的问题。

Answer 1

这是我使用延迟传播实现的分段树片段。希望这会帮助你。

#define int long long
#define MAX 100005*3

int  stree[MAX],lazy[MAX];

void update(int  cur,int  cur_lft,int  cur_rgt,int  st,int  en,int  val)
{
    if(cur_lft>en || cur_rgt<st) return ;
    if(cur_lft>=st && cur_rgt<=en)
    {
        stree[cur]+=val*(cur_rgt-cur_lft+1);
        lazy[cur]+=val;
        return;
    }
    int  l=cur<<1,r=(cur<<1)+1,mid=(cur_lft+cur_rgt)>>1;
    update(l,cur_lft,mid,st,en,val);
    update(r,mid+1,cur_rgt,st,en,val);
    stree[cur]=stree[l]+stree[r]+lazy[cur]*(cur_rgt-cur_lft+1);
}

int  query(int  cur,int  cur_lft,int  cur_rgt,int  st,int  en,int  lzy)
{
    if(cur_lft>en || cur_rgt<st) return 0;
    if(cur_lft>=st && cur_rgt<=en) return stree[cur]+lzy*(cur_rgt-cur_lft+1);
    int  l=cur<<1,r=(cur<<1)+1,mid=(cur_lft+cur_rgt)>>1;
    int  left_tree=query(l,cur_lft,mid,st,en,lzy+lazy[cur]);
    int  right_tree=query(r,mid+1,cur_rgt,st,en,lzy+lazy[cur]);
    return left_tree+right_tree;
}

编辑 要更新和查询段树，我们可以调用以下函数：

query(1,0,n-1,lower_range,upper_range,0));
update(1,0,n-1,lower_range,upper_range,v);