分块 70pts 后3点TLE

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll sum[100007], l[100007], r[100007], arr[100007], idx[100007], k;
ll block, num, n, m, opt, x, y;

ll query () {
    ll res = 0;
    if (idx[x] == idx[y]) {
        for (int i = x; i <= y; i++) {
            res += arr[i];
        }
        return res;
    }
    for (int i = x; i <= r[idx[x]]; i++) {
        res += arr[i];
    }
    for (int i = idx[x] + 1; i <= idx[y] - 1; i++) {
        res += sum[i];
    }
    for (int i = l[idx[y]]; i <= y; i++) {
        res += arr[i];
    }
    return res;
}

void build () {
    block = sqrt(n);
    num = n / block;
    if (n % block != 0) {
        num++;
    }
    for (int i = 1; i <= num; i++) {
        l[i] = (i - 1) * block + 1, r[i] = i * block;
    }
    for (int i = 1; i <= n; i++) {
        idx[i] = (i - 1) / block + 1;
    }
    r[num] = n;
    for (int i = 1; i <= num; i++) {
        for (int j = l[i]; j <= r[i]; j++) {
            sum[i] += arr[j];
        }
    }
}

int main () {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    build();
    for (int i = 1; i <= m; i++) {
        cin >> opt >> x >> y;
        if (opt == 1) {
            cin >> k;
            for (int j = x; j <= y; j++) {
                arr[j] += k, sum[idx[j]] += k;
            }
        } else {
            cout << query() << endl;
        }
    }
    return 0;
}