线段树

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100001;
ll sum[N*4];
ll tag[N*4];
int a[N];
void pushdown(int x, int l_len, int r_len) {
    tag[x*2] += tag[x];
    sum[x*2] += l_len * tag[x];
    tag[x*2+1] += tag[x];
    sum[x*2+1] += r_len * tag[x];
    tag[x] = 0;
}
void build(int x, int l, int r) {
    if (l == r) {
        sum[x] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(x*2, l, mid);
    build(x*2+1, mid+1, r);
    sum[x] = sum[x*2] + sum[x*2+1];
}
void add(int x, int l, int r, int L, int R, int val) {
    //x:线段树节点编号
	//[l,r]：当前线段树节点的代表区间
	//[L,R]：要修改的区间
	//val：增加的值
	if (L <= l && r <= R) {//这个线段树区间可以代表一部分修改区间
        tag[x] += val;
        sum[x] += (r - l + 1) * val;
        return;
    }
    int mid = (l + r) / 2;
    if (tag[x]) pushdown(x, mid-l+1, r-mid);
    if (L <= mid) add(x*2, l, mid, L, R, val);//不能代表
    if (mid < R) add(x*2+1, mid+1, r, L, R, val);//到左右儿子继续查找
    sum[x] = sum[x*2] + sum[x*2+1];
}//修改
ll query(int x, int l, int r, int L, int R) {
    if (L <= l && r <= R)
        return sum[x];
    int mid = (l + r) / 2;
    if (tag[x]) pushdown(x, mid-l+1, r-mid);
    ll res = 0ll;
    if (L <= mid) res += query(x*2, l, mid, L, R);
    if (mid < R) res += query(x*2+1, mid+1, r, L, R);
    sum[x] = sum[x*2] + sum[x*2+1];
    return res;
}//查询
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    build(1, 1, n);
    while (m--) {
        int op, x, y, k;
        scanf("%d%d%d", &op, &x, &y);
        if (op == 1) {
            scanf("%d", &k);
            add(1, 1, n, x, y, k);
        } else {
            printf("%lld\n", query(1, 1, n, x, y));
        }
    }
    return 0;
}