这里学的时候写的注释是“延迟更新”，含义和“懒标记”相同。 一直卡在70分，最后三个全部TLE。

#include <iostream>
#include <vector>
#include <string>

using namespace std;


class SegmentTree {

private:

    vector<long long> tree;
    vector<long long> lazy;
    size_t n;

    inline void buildTree(const vector<int> &data, int treeIndex, int l, int r) {
        if (l == r) {
            tree[treeIndex] = data[l];
            return;
        }
        int mid = l + ((r - l) >> 1);
        long long dou_ti = treeIndex << 1;
        buildTree(data, dou_ti + 1, l, mid);
        buildTree(data, dou_ti + 2, mid + 1, r);
        // 在后序递归位置，逐步将各个小区间和合并成大区间。
        tree[treeIndex] = tree[dou_ti + 1] + tree[dou_ti + 2];
    }

    inline long long queryRange(int treeIndex, int sl, int sr, int l, int r) {
        if (sl == l && sr == r) {
            return tree[treeIndex];
        }
        // 每次访问一个节点都要检查其延迟更新的状态，否则会导致没有完成更新的错误。
        pushDown(treeIndex, sl, sr);
        int mid = sl + ((sr - sl) >> 1);
        int dou_ti = treeIndex << 1;
        if (r <= mid) {
            // 查询的区间完全在左子区间中
            return queryRange(dou_ti + 1, sl, mid, l, r);
        } else if (l > mid) {
            // 查询的区间完全在右子区间中
            return queryRange(dou_ti + 2, mid + 1, sr, l, r);
        } else {
            // 查询的区间与左右子区间交错
            return queryRange(dou_ti + 1, sl, mid, l, mid)
                   +
                   queryRange(dou_ti + 2, mid + 1, sr, mid + 1, r);
        }
    }

    inline void pushDown(int treeIndex, int l, int r) {
        if (lazy[treeIndex] != 0) {
            int mid = l + ((r - l) >> 1);
            long long dou_ti = treeIndex << 1;
            // 将当前节点的延迟更新应用到左右子节点
            // 解释：
            // [l, mid]一共有mid - l + 1个节点，如果给[l, r]全部增加lazy[treeIndex]，
            // 那么[l, mid]所代表的节点的区间和应该增加lazy[treeIndex] * (mid - l + 1)
            // [mid + 1, r]同理
            tree[dou_ti + 1] += lazy[treeIndex] * (mid - l + 1);
            tree[dou_ti + 2] += lazy[treeIndex] * (r - mid);
            // 更新左右子节点的延迟更新值，以便记录它们的子节点的未更新的值
            lazy[dou_ti + 1] += lazy[treeIndex];
            lazy[dou_ti + 2] += lazy[treeIndex];
            // 当前节点的延迟更新已经应用完毕，因此要清除。
            lazy[treeIndex] = 0;
        }
    }

    inline void updateRange(int treeIndex, int sl, int sr, int l, int r, long long val) {
        if (sl == r && sr == r) {
            tree[treeIndex] += val * (r - l + 1);
            lazy[treeIndex] += val;
            return ;
        }
        // 只要访问到了就一定要检查延迟更新的状态
        pushDown(treeIndex, sl, sr);
        int mid = sl + ((sr - sl) >> 1);
        int dou_ti = treeIndex << 1;

        // 这里和区间查询的逻辑差不多，区别只有如下两个
        // 多带了一个参数"val"，
        // 在后序递归位置进行的更新操作（其实和buildTree时的操作差不多）。
        if (r <= mid) {
            updateRange(dou_ti + 1, sl, mid, l, r, val);
        } else if (l > mid) {
            updateRange(dou_ti + 2, mid + 1, sr, l, r, val);
        } else {
            updateRange(dou_ti + 1, sl, mid, l, mid, val),
            updateRange(dou_ti + 2, mid + 1, sr, mid + 1, r, val);
        }

        tree[treeIndex] = tree[dou_ti + 1] + tree[dou_ti + 2];

    }

public:
    explicit SegmentTree(const vector<int> &data) {
        n = data.size();
        size_t fn = 4 * n;
        tree.resize(fn);
        lazy.resize(fn, 0);
        buildTree(data, 0, 0, n - 1);
    }

    inline long long query(int l, int r) {
        return queryRange(0, 0, n - 1, l, r);
    }

    inline void update(int l, int r, long long val) {
        updateRange(0, 0, n - 1, l, r, val);
    }

};
int read()
{
    int c = getchar(), f = 1, res = 0;
    while (c > '9' || c < '0') {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c <= '9' && c >= '0') res = (res << 1) + (res << 3) + (c - '0'), c = getchar();
    return res;
}
int main() {
//    ios::sync_with_stdio(false);
//    cin.tie(0);
    int n = read(), m = read();
    vector<int> data(n);
    for (int i = 0; i < n; ++i) cin >> data[i];

    SegmentTree st(data);

    while (m--) {
        int type = read(), x = read(), y = read();
        long long k;
        x--, y--;
        if (type == 1) {
            k = read();
            st.update(x, y, k);
        } else if (type == 2) {
            printf("%lld\n", st.query(x, y));
        } else {
            throw "ERROR TYPE" + to_string(type);
        }
    }

}