一片伟大的净土

灵魂的归处,肉体的坟墓。

线段树的懒标记

2024/4/8

add函数中
if(x<=l&&y>=r){
        tag[i]+=k;
        st[i]+=k*(r-l+1);
        return ;
    }
    
新增push_down,在add和query中都要调用
void push_down(int l,int r,int i){
    if(tag[i]){
        int mid=(l+r)>>1;
        tag[lc(i)]+=tag[i];
        tag[rc(i)]+=tag[i];
        st[lc(i)]+=tag[i]*(mid-l+1);
        st[rc(i)]+=tag[i]*(r-mid);
        tag[i]=0;
    }
}