【luogu3372】线段树 1 模板

            

题面

已知一个数列,你需要进行下面两种操作:
1.将某区间每一个数加上x
2.求出某区间每一个数的和

题解

区间修改+区间查询
线段树模板

#include
#define maxn 100010
#define lch p<<1
#define rch p<<1|1
using namespace std;
typedef long long LL;
struct node{
    LL val, addmark;
}sgt[maxn<<2];
void pushdown(LL p, LL l, LL r){
    if(sgt[p].addmark != 0){
        LL t = sgt[p].addmark, m = l+r>>1;
        sgt[lch].addmark += t;
        sgt[rch].addmark += t;
        sgt[lch].val += t*(m-l+1);
        sgt[rch].val += t*(r-m);
        sgt[p].addmark = 0;
    }
}
void update(LL p, LL l, LL r, LL L, LL R, LL v){
    if(l > R || r < L)return ;  //越界返回
    if(L <= l && R >= r){
        sgt[p].addmark += v;
        sgt[p].val += v*(r-l+1);
        return ;
    }
    pushdown(p, l, r);//记得pushdown 的位置  每次递归前
    LL m = l+r>>1;
    update(lch, l, m, L, R, v);
    update(rch, m+1, r, L, R, v);
    sgt[p].val = sgt[lch].val + sgt[rch].val;
}
LL query(LL p, LL l, LL r, LL L, LL R){
    if(l > R || r < L)return 0;  //越界返回
    if(L <= l && R >= r)return sgt[p].val;
    pushdown(p,l,r);
    LL m = l+r>>1, ans = 0;
    ans += query(lch, l, m, L , R);
    ans += query(rch, m+1, r, L , R);
    return ans;
}
int main(){
    LL n, m;
    cin>>n>>m;
    for(int i = 1; i <= n; i++){
        LL x;  cin>>x;
        update(1, 1, n, i, i, x);
    }
    for(int i = 1; i <= m; i++){
        LL op;  cin>>op;
        if(op == 1){
            LL x, y, k;  cin>>x>>y>>k;
            update(1,1,n,x,y,k);
        }else{
            LL x, y;  cin>>x>>y;
            cout<1, 1, n, x, y)<<"\n";
        }
    }
    return 0;
}
点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像