数据结构-段树，延迟传播

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);