萌新求助线段树模板10pts

xiaoyang222 @ 2024-05-18 09:22:22

#include <iostream>
#define int long long
using namespace std;
const int N=1e5+5;
const int MOD=1e9+7;
int tree[N<<2];
int tag[N];//加 
int t[N];
void up(int u,int l,int r){
    tree[u]=tree[u<<1]+tree[u<<1|1];
}
void upd(int u,int l,int r,int num){
    tree[u]+=num*(r-l+1);
    tag[u]+=num;
}
void pushdown(int u,int l,int r){
    int mid=l+r>>1;
    upd(u<<1,l,mid,tag[u]);
    upd(u<<1|1,mid+1,r,tag[u]);
    tag[u]=0;
}
void init(int l,int r,int id){//建树
    if (l==r){
        tree[id]=t[l];
        return;
    } 
    int mid=l+r>>1;
    init(l,mid,id<<1);/*左儿子*/init(mid+1,r,id<<1|1);/*右儿子*/
    up(id,l,r);
}
int query(int l,int r,int u,int x,int y){
    if (x<=l && y>=r){//完全包含 
        return tree[u];
    }
    int mid=l+r>>1;
    int res=0;
    pushdown(u,l,r);
    if (x<=mid) res+=query(l,mid,u<<1,x,y);
    if (y>=mid+1) res+=query(mid+1,r,u<<1|1,x,y);
    return res;
}
void modify(int l,int r,int u,int x,int y,int num/*加上的数*/){
    if (l>=x && r<=y){//完全包含
        upd(u,l,r,num);
        return; 
    }
    if (l>y || r<x){//完全不包含 
        return;
    }
    int mid=l+r>>1;
    modify(l,mid,u<<1,x,y,num);
    modify(mid+1,r,u<<1|1,x,y,num);
    up(u,l,r);
}
signed main(){
    int n,m;
    cin >> n >> m;
    for (int i=1;i<=n;++i){
        scanf("%lld",&t[i]); 
    }
    init(1,n,1);
    int op,a,b,c;
    for (int _=0;_<m;++_){
        scanf("%lld%lld%lld",&op,&a,&b);
        if (op==2){
            printf("%lld\n",query(1,n,1,a,b));
        }else{
            scanf("%lld",&c);
            modify(1,n,1,a,b,c);
        }
//      for (int i=1;i<=n;++i){
//          cout<<query(1,n,1,i,i)<<" ";
//      }
//      cout<<endl;
//      cout<<query(1,n,1,1,3)<<endl;
    }
    return 0;
}

by _XiAo__ @ 2024-05-18 09:27:54

没太看懂，为什么query的判完全包含和modify的不一样

by _XiAo__ @ 2024-05-18 09:29:07

是不是modify判反了

by senak @ 2024-05-18 09:29:33

区间修改要pushdown

by _XiAo__ @ 2024-05-18 09:31:15

t数组也开小了

by xiaoyang222 @ 2024-05-18 09:43:12

@xiang_ling @senak 好的我再看看，谢了

by xiaoyang222 @ 2024-05-18 09:46:00

好的，70pts 了

#include <iostream>
#define int long long
using namespace std;
const int N=1e5+5;
const int MOD=1e9+7;
int tree[N<<2];
int tag[N];//加 
int t[N];
void up(int u,int l,int r){
    tree[u]=tree[u<<1]+tree[u<<1|1];
}
void upd(int u,int l,int r,int num){
    tree[u]+=num*(r-l+1);
    tag[u]+=num;
}
void pushdown(int u,int l,int r){
    int mid=l+r>>1;
    upd(u<<1,l,mid,tag[u]);
    upd(u<<1|1,mid+1,r,tag[u]);
    tag[u]=0;
}
void init(int l,int r,int id){//建树
    if (l==r){
        tree[id]=t[l];
        return;
    } 
    int mid=l+r>>1;
    init(l,mid,id<<1);/*左儿子*/init(mid+1,r,id<<1|1);/*右儿子*/
    up(id,l,r);
}
int query(int l,int r,int u,int x,int y){
    if (x<=l && y>=r){//完全包含 
        return tree[u];
    }
    int mid=l+r>>1;
    int res=0;
    pushdown(u,l,r);
    if (x<=mid) res+=query(l,mid,u<<1,x,y);
    if (y>=mid+1) res+=query(mid+1,r,u<<1|1,x,y);
    return res;
}
void modify(int l,int r,int u,int x,int y,int num/*加上的数*/){
    if (l>=x && r<=y){//完全包含
        upd(u,l,r,num);
        return; 
    }
    int mid=l+r>>1;
    pushdown(u,l,r);
    if (x<=mid) modify(l,mid,u<<1,x,y,num);
    if (mid<y) modify(mid+1,r,u<<1|1,x,y,num);
    up(u,l,r);
}
signed main(){
    int n,m;
    cin >> n >> m;
    for (int i=1;i<=n;++i){
        scanf("%lld",&t[i]); 
    }
    init(1,n,1);
    int op,a,b,c;
    for (int _=0;_<m;++_){
        scanf("%lld%lld%lld",&op,&a,&b);
        if (op==2){
            printf("%lld\n",query(1,n,1,a,b));
        }else{
            scanf("%lld",&c);
            modify(1,n,1,a,b,c);
        }
//      for (int i=1;i<=n;++i){
//          cout<<query(1,n,1,i,i)<<" ";
//      }
//      cout<<endl;
//      cout<<query(1,n,1,1,3)<<endl;
    }
    return 0;
}

by xiaoyang222 @ 2024-05-18 09:46:52

艹数组开小了，过了。

谢谢两位大佬。