RT, 线段树1用分块写

#include<bits/stdc++.h>

namespace IO {
    inline int read() {
        int ret = 0, f = 1;char ch = getchar();
        while (ch < '0' || ch > '9') {
            if (ch == '-') f = -f;
            ch = getchar();
        }
        while (ch >= '0' && ch <= '9') {
            ret = (ret << 1) + (ret << 3) + (ch ^ 48);
            ch = getchar();
        }
        return ret * f;
    }
    void write(int x) {
        if (x < 0) putchar('-'), x = -x;
        if (x > 9) write(x / 10);
        putchar(x % 10 + '0');
    }
}

using namespace std;
using namespace IO;

const int maxn = 1e5 + 5;

int a[maxn], tag[maxn], sum[maxn], f[maxn], L[maxn], R[maxn];
int n, m, len;

int query(int l, int r) {
    int fr = f[l], to = f[r], ans = 0;
    if (fr == to) {
        for (int i = l;i <= r;i++) ans += a[i] + tag[i];
        return ans;
    }
    for (int i = fr + 1;i < to;i++) ans += sum[i];
    for (int i = l;i <= R[fr];i++) ans += a[i] + tag[fr];
    for (int i = L[to];i <= r;i++) ans += a[i] + tag[to];
    return ans;
}

void update(int l, int r, int k) {
    int fr = f[l], to = f[r];
    if (fr == to) {
        for (int i = l;i <= r;i++) a[i] += k, sum[fr] += k;     
        return;
    }
    for (int i = fr + 1;i < to;i++) tag[i] += k, sum[i] += k * (R[i] - L[i] + 1);
    for (int i = l;i <= R[fr];i++) a[i] += k, sum[fr] += k;
    for (int i = L[to];i <= r;i++) a[i] += k, sum[to] += k;
    return;
}

void init() {
    len = sqrt(n);
    for (int i = 1;i <= len;i++) {
        L[i] = (i - 1) * len + 1;
        R[i] = i * len;
        for (int j = L[i];j <= R[i];j++) {
            f[j] = i;
            sum[j] += a[i];
        }
    }
    if (R[len] != n) {
        len++;
        L[len] = R[len - 1] + 1;
        R[len] = n;
        for (int i = L[len];i <= R[len];i++) {
            f[i] = len;
            sum[len] += a[i];
        }
    }
}

int main() {
    n = read(), m = read();
    for (int i = 1;i <= n;i++) a[i] = read();

    init();

    while (m--) {
        int op = read(), x = read(), y = read(), k;
        if (op == 1) {
            k = read();
            update(x, y, k);
        }
        else write(query(x, y)), puts("");
    }

    return 0;
}