线段树

#include <iostream>
using namespace std;

const int N = 100010;

int a[N];       // 原始数组
long long tree[4*N];  // 线段树：每个节点存对应区间的和
long long lazy[4*N];  // 懒惰标记：延迟下传的修改量
int n;          // 数组大小

// pushUp：用左右子节点的值更新当前节点
// 当前节点的值 = 左子 + 右子
void pushUp(int node) {
    tree[node] = tree[node*2] + tree[node*2+1];
}

// pushDown：把懒惰标记下传给左右子节点
// 当某个节点有 lazy 值没下传时调用
void pushDown(int node, int l, int r) {
    if (lazy[node] == 0) return;  // 没有需要下传的修改
    int mid = (l + r) / 2;
    // 左子区间 [l, mid]，长度 = mid-l+1
    tree[node*2]   += lazy[node] * (mid - l + 1);
    lazy[node*2]   += lazy[node];
    // 右子区间 [mid+1, r]，长度 = r-mid
    tree[node*2+1] += lazy[node] * (r - mid);
    lazy[node*2+1] += lazy[node];
    // 当前节点的标记已下传，清零
    lazy[node] = 0;
}

// 建树：递归构建线段树
// node=当前节点编号, [l,r]=当前节点管辖的区间
void build(int node, int l, int r) {
    if (l == r) {
        // 叶子节点：直接等于原始数组的值
        tree[node] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(node*2,   l,   mid);  // 递归建左子树
    build(node*2+1, mid+1, r);  // 递归建右子树
    pushUp(node);               // 用子节点更新当前节点
}

// 区间修改：把 [ql, qr] 内的所有元素加上 val
void update(int node, int l, int r, int ql, int qr, long long val) {
    if (ql <= l && r <= qr) {
        // 当前区间完全被查询区间覆盖
        tree[node] += val * (r - l + 1);  // 区间和增加 val×长度
        lazy[node] += val;                // 记录懒惰标记，暂不下传
        return;
    }
    // 部分覆盖：需要递归到子节点
    pushDown(node, l, r);  // 先下传懒惰标记
    int mid = (l + r) / 2;
    if (ql <= mid) update(node*2,   l,   mid, ql, qr, val);
    if (qr > mid)  update(node*2+1, mid+1, r, ql, qr, val);
    pushUp(node);  // 子节点更新后，更新当前节点
}

// 区间查询：求 [ql, qr] 的和
long long query(int node, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return tree[node];  // 完全覆盖，直接返回
    }
    pushDown(node, l, r);  // 先下传懒惰标记
    int mid = (l + r) / 2;
    long long res = 0;
    if (ql <= mid) res += query(node*2,   l,   mid, ql, qr);
    if (qr > mid)  res += query(node*2+1, mid+1, r, ql, qr);
    return res;
}

int main() {
    int q;  // 操作次数
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];

    build(1, 1, n);  // 建树，根节点编号为1

    while (q--) {
        int op;
        cin >> op;
        if (op == 1) {
            // 区间修改：把 l 到 r 的每个元素加上 x
            int l, r; long long x;
            cin >> l >> r >> x;
            update(1, 1, n, l, r, x);
        } else {
            // 区间查询：求 l 到 r 的和
            int l, r;
            cin >> l >> r;
            cout << query(1, 1, n, l, r) << endl;
        }
    }
    return 0;
}