data-structures - セグメントツリー、怠惰な伝播

Question

この構造がどのように機能し、どのように更新するかについては良い考えがありますが、Lazy Propagationで機能する場合は、何をすべきかわかりません。多くの問題で、これが競技会に合格する必要があるため、方法を知りたいです。それを機能させるために。

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