树状数组

区间修改 区间查询

前缀和 差分

/**
 * 树状数组
 * 区间修改 区间查询
 * 前缀和 差分
 */
#include <bits/stdc++.h>

using namespace std;
const int maxn = 100005;
typedef long long ll;
int n, m;
ll sum[maxn], t1[maxn], t2[maxn];

void add1(int x, ll k){
    for(; x <= n; x += x & -x) t1[x] += k;
}

ll ask1(int x){
    ll ans = 0;
    for(; x; x -= x & -x) ans += t1[x];
    return ans;
}

void add2(int x, ll k){
    for(; x <= n; x += x & -x) t2[x] += k;
}

ll ask2(int x){
    ll ans = 0;
    for(; x; x -= x & -x) ans += t2[x];
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for(int i = 1, x; i <= n; ++ i){
        cin >> x;
        sum[i] = sum[i - 1] + x;
    }

    while(m --){
        char op;
        int l, r;
        ll z;
        cin >> op;
        if(op == 'Q'){
            cin >> l >> r;
            ll ans = sum[r] + (r + 1) * ask1(r) - ask2(r);
            ans -= sum[l - 1] + l * ask1(l - 1) - ask2(l - 1);
            cout << ans << endl;
        }else{
            cin >> l >> r >> z;
            add1(l, z);
            add1(r + 1, -z);
            add2(l, l * z);
            add2(r + 1, - (r + 1) * z);
        }
    }

    return 0;
}

线段树 lazy标记

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
int n, m;
const int maxn = 100005;
ll a[maxn];
struct Node{
    int l, r;
    ll sum, lazy;
}t[maxn * 4];

void build(int p, int l, int r){
    t[p].l = l, t[p].r = r;
    if(l == r){t[p].sum = a[l]; return; }
    int mid = l + r >> 1;
    build(2 * p, l, mid);
    build(2 * p + 1, mid + 1, r);
    t[p].sum = t[2 * p].sum + t[2 * p + 1].sum;
}

void spread(int p){
    if(t[p].lazy){
        t[2 * p].sum += t[p].lazy * (t[2 * p].r - t[2 * p].l + 1);
        t[2 * p + 1].sum += t[p].lazy * (t[2 * p + 1].r - t[2 * p + 1].l + 1);
        t[2 * p].lazy += t[p].lazy; //注意是 "+=" 不是 "="
        t[2 * p + 1].lazy += t[p].lazy;
        t[p].lazy = 0;
    }
}

void change(int p, int l, int r, ll d){
    if(t[p].l >= l && t[p].r <= r) {
        t[p].sum += d * (t[p].r - t[p].l + 1);
        t[p].lazy += d;  //注意是 "+=" 不是 "="
        return;
    }
    spread(p);
    int mid = t[p].l + t[p].r >> 1;
    if(l <= mid) change(2 * p, l, r, d);
    if(r > mid) change(2 * p + 1, l, r, d);
    t[p].sum = t[2 * p].sum + t[2 * p + 1].sum;
}

ll ask(int p, int l, int r){
   if(t[p].l >= l && t[p].r <= r) return t[p].sum;
   int mid = t[p].l + t[p].r >> 1;
   spread(p);
   ll res = 0;
   if(l <= mid) res += ask(2 * p, l, r);
   if(r > mid) res += ask(2 * p + 1, l, r);
   return res;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n >> m;
    for(int i = 1; i <= n; ++ i) cin >> a[i];
    build(1, 1, n);

    while(m --){
        char op;
        cin >> op;
        if(op == 'Q'){
            int l, r;
            cin >> l >> r;
            cout << ask(1, l, r) << endl;
        }else{
            int l, r;
            ll val;
            cin >> l >> r >> val;
            change(1, l, r, val);
        }
    }
    return 0;
}

分块

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 100005;
int n, m, t;
ll a[maxn], sum[maxn], add[maxn];
int L[maxn], R[maxn], pos[maxn];

void change(int l, int r, ll d){
    int lpos = pos[l], rpos = pos[r];
    if(lpos == rpos){
        for(int i = l; i <= r; ++ i) a[i] += d;
        sum[lpos] += (r - l + 1) * d;
    }else{
        for(int i = l; i <= R[lpos]; ++ i) a[i] += d;
        sum[lpos] += (R[lpos] - l + 1) * d;
        for(int i = L[rpos]; i <= r; ++ i) a[i] += d;
        sum[rpos] += (r - L[rpos] + 1) * d;
        for(int i = lpos + 1; i < rpos; ++ i) add[i] += d;
    }
}

ll query(int l, int r){
    ll ret = 0;
    int lpos = pos[l], rpos = pos[r];
    if(lpos == rpos){
        for(int i = l; i <= r; ++ i) ret += a[i];
        ret += add[lpos] * (r - l + 1);
    }else{
        for(int i = lpos + 1; i < rpos; ++ i) ret += sum[i] + (R[i] - L[i] + 1) * add[i];
        for(int i = l; i <= R[lpos]; ++ i) ret += a[i];
        ret += add[lpos] * (R[lpos] - l + 1);
        for(int i = L[rpos]; i <= r; ++ i) ret += a[i];
        ret += add[rpos] * (r - L[rpos] + 1);
    }
    return ret;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i) cin >> a[i];
    //分块
    t = sqrt(n);
    for(int i = 1; i <= t; ++ i){
        L[i] = (i - 1) * sqrt(n) + 1;
        R[i] = i * sqrt(n);
    }
    if(R[t] < n){
        L[t + 1] = R[t] + 1;
        R[t + 1] = n;
        t ++;
    }
    //预处理
    for(int i = 1; i <= t; ++ i){
        for(int j = L[i]; j <= R[i]; ++ j){
            pos[j] = i;
            sum[i] += a[j];
        }
    }
    //solve
    while(m --){
        char op;
        cin >> op;
        if(op == 'Q'){
            int l, r;
            cin >> l >> r;
            cout << query(l, r) << endl;
        }else{
            int l, r;
            ll val;
            cin >> l >> r >> val;
            change(l, r, val);
        }
    }
}