关于线段树
  • 板块学术版
  • 楼主Masna_Kimoyo
  • 当前回复40
  • 已保存回复40
  • 发布时间2021/9/1 20:08
  • 上次更新2023/11/4 08:10:58
查看原帖
关于线段树
199459
Masna_Kimoyo楼主2021/9/1 20:08

今天复习线段树,有个地方还是蒙了()

这是区间加法的一段题解

inline void push_down(ll p,ll l,ll r)
{
    ll mid=(l+r)>>1;
    f(ls(p),l,mid,tag[p]);
    f(rs(p),mid+1,r,tag[p]);
    tag[p]=0;
}
inline void update(ll nl,ll nr,ll l,ll r,ll p,ll k)
{
    if(nl<=l&&r<=nr)
    {
        ans[p]+=k*(r-l+1);
        tag[p]+=k;
        return ;
    }
    push_down(p,l,r);
    ll mid=(l+r)>>1;
    if(nl<=mid)update(nl,nr,l,mid,ls(p),k);
    if(nr>mid) update(nl,nr,mid+1,r,rs(p),k);
    push_up(p);
}

有一个地方不懂,假如一个点满足 nl<=l&&r<=nr ,那就会

ans[p]+=k*(r-l+1);
tag[p]+=k;
return ;

可是这个点上一次已经 push_down 过了,那不就相当于操作了两次吗

还有一个问题

这里有个 r-l+1 ,但是如果当前需要修改的区间,中间有点不在修改范围内,那这个sum不就是错的吗

2021/9/1 20:08
加载中...