树状数组&线段树

树状数组

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N=100005;

int n, m;
int a[N];
LL tr1[N]; // 维护b[i]的前缀和
LL tr2[N]; // 维护b[i]*i的前缀和

int lowbit(int x){return x & -x;}
void add(LL tr[], int x, LL c){ // 更新树状数组
    for(int i=x; i<=n; i+=lowbit(i)) tr[i]+=c;
}
LL sum(LL tr[], int x){
    LL ans=0;
    for(int i=x; i; i-=lowbit(i)) ans+=tr[i];
    return ans;
}

LL prefix_sum(int x){
    return sum(tr1, x)*(x+1)-sum(tr2, x);
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; ++i) scanf("%d", &a[i]);
    for(int i=1; i<=n; ++i){
        int b=a[i]-a[i-1];
        add(tr1, i, b);
        add(tr2, i, (LL)b*i);
    }
    while(m--){
        char ch[2];
        int l, r, d;
        scanf("%s%d%d", &ch, &l, &r);
        if(ch[0]=='Q'){
            printf("%lld\n", prefix_sum(r)-prefix_sum(l-1));
        }
        else{
            scanf("%d", &d);
            add(tr1, l, d);
            add(tr2, l, l*d);
            add(tr1, r+1, -d);
            add(tr2, r+1, (r+1)*(-d));
        }
    }

    return 0;
}

线段树(懒标记)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

typedef long long LL;
const int N=100005;
int n, m, a[N];
struct Node{
    int l, r;
    LL sum; // 存储总和
    LL tag; // 存储懒标记
}tr[N<<2];

inline void pushup(int u){tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;}
inline void pushdown(int u){
    Node &root =tr[u];
    Node &left=tr[u<<1];
    Node &right=tr[u<<1|1];
    if(root.tag){
        left.tag+=root.tag;
        left.sum+=(LL)(left.r-left.l+1)*root.tag;
        right.tag+=root.tag;
        right.sum+=(LL)(right.r-right.l+1)*root.tag;
        root.tag=0; // 父节点懒标记分解
    }
}

void build(int u, int l, int r){
    if(l==r) tr[u]={l, r, a[l], 0};
    else{
        tr[u]={l, r};
        int mid=l+r>>1;
        build(u<<1, l, mid);
        build(u<<1|1, mid+1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int d){
    if(tr[u].l>=l && tr[u].r<=r){
        tr[u].sum+=(LL)(tr[u].r-tr[u].l+1)*d;
        tr[u].tag+=d;
    }
    else{
        pushdown(u);
        int mid=tr[u].l+tr[u].r>>1;
        if(l<=mid) modify(u<<1, l, r, d);
        if(r>mid) modify(u<<1|1, l, r, d);
        pushup(u);
    }
}

LL query(int u, int l, int r){
    if(tr[u].l>=l && tr[u].r<=r) return tr[u].sum;
    pushdown(u);
    int mid=tr[u].l+tr[u].r>>1;
    LL ans=0;
    if(l<=mid) ans+=query(u<<1, l, r);
    if(r>mid) ans+=query(u<<1|1, l, r);
    return ans;
}

int main(){
    cin>>n>>m;
    for(int i=1; i<=n; ++i) scanf("%d", &a[i]);
    build(1, 1, n);
    char op[2];
    int l, r, d;
    while(m--){
        scanf("%s%d%d", &op, &l, &r);
        if(op[0]=='C'){
            scanf("%d", &d);
            modify(1, l, r, d);
        }
        else cout<<query(1, l, r)<<endl;
    }
    return 0;
}