POJ 3468 A Simple Problem with Integers （线段树+成段更新）

题意：给你N个数，然后有M个操作。有两种类型的操作，（1）“C a b c”，表示将区间[a,b]里的数加上c。（2）“Q a b”，表示查询区间[a,b]的数的和。

题解：线段树+成段更新
开long long

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<fstream>
#include<set>
#include<map>
#include<sstream>
#include<iomanip>
#define ll long long
using namespace std;
const int MAXN = 1e5 + 5;
ll sum[MAXN << 2], add[MAXN << 2];
struct Node {
    int l, r;
    int mid() { return (l + r) >> 1; }
} tree[MAXN << 2];

void PushDown(int rt, int m) {
    if (add[rt]) {
        add[rt << 1] += add[rt];
        add[rt << 1 | 1] += add[rt];
        sum[rt << 1] += add[rt] * (m - (m >> 1));
        sum[rt << 1 | 1] += add[rt] * (m >> 1);
        add[rt] = 0;
    }
}
void build(int l, int r, int rt) {
    tree[rt].l = l;
    tree[rt].r = r;
    add[rt] = 0;
    if (l == r) {
        scanf("%lld", &sum[rt]);
        return;
    }
    int m = tree[rt].mid();
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void update(int c, int l, int r, int rt) {
    if (tree[rt].l == l && r == tree[rt].r) {
        add[rt] += c;
        sum[rt] += c * (r - l + 1);
        return;
    }
    if (tree[rt].l == tree[rt].r) return;
    PushDown(rt, tree[rt].r - tree[rt].l + 1);
    int m = tree[rt].mid();
    if (r <= m) update(c, l, r, rt << 1);
    else if (l > m) update(c, l, r, rt << 1 | 1);
    else {
        update(c, l, m, rt << 1);
        update(c, m + 1, r, rt << 1 | 1);
    }
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
ll query(int l, int r, int rt) {
    if (l == tree[rt].l && r == tree[rt].r) {
        return sum[rt];
    }
    PushDown(rt, tree[rt].r - tree[rt].l + 1);
    int m = tree[rt].mid();
    ll res = 0;
    if (r <= m) res += query(l, r, rt << 1);
    else if (l > m) res += query(l, r, rt << 1 | 1);
    else {
        res += query(l, m, rt << 1);
        res += query(m + 1, r, rt << 1 | 1);
    }
    return res;
}
int n, q, x, y, w;
char s[1];
int main() {
    scanf("%d%d", &n, &q);
    build(1, n, 1);
    while (q--) {
        scanf("%s", s);
        if (s[0] == 'C') {
            scanf("%d%d%d", &x, &y, &w);
            update(w, x, y, 1);
        }
        else {
            scanf("%d%d", &x, &y);
            printf("%lld\n", query(x, y, 1));
        }
    }
    return 0;
}