区间修改求助

P3372 【模板】线段树 1

ZM____ML @ 2023-05-13 20:38:02

inline int change(int l,int r,int cnt,int ll,int rr,int v){
    if(l<ll||r>rr)return sum[cnt];//?
    if(l>=ll&&r<=rr){
        mark[cnt]+=v;
        return sum[cnt]+=v*(r-l+1);
    }
    int mid=l+r>>1;
    push_down(l,r,cnt);
    return change(l,mid,cnt<<1,ll,rr,v)+change(mid+1,r,cnt<<1|1,ll,rr,v);
}

就是这一段代码,加?的这个特判去掉就执行不了,区间查询没问题,修改出错。


by _fairytale_ @ 2023-05-13 20:57:22

能发个完整代码吗

没见过change函数还写int的...


by _fairytale_ @ 2023-05-13 21:02:50

哦我知道了 你把最后一行改成

if(mid>=ll)return change(l,mid,cnt<<1,ll,rr,v);
if(mid<rr)return change(mid+1,r,cnt<<1|1,ll,rr,v);

试试

两边子树一直递归修改肯定会出问题


|