线段树入门

// 标准答案 —— 什么结构都不用：区间加就一格一格地加，区间查就一格一格地累。
//
// 为什么它存在：
//   ① 它是对拍里的那份**标准答案**。思路和线段树完全不同（第 9、15 章那条规矩：
//      标准答案最好用另一种思路写，同一个思路写两遍只能验出打字错误）。
//   ② ★ 它同时是这一章的「反面教材」：**改 O(区间长)、查 O(区间长)**，两边都是线性。
//      第 38 章那两个暴力（原数组 / 前缀和）好歹各有一端是 O(1)，
//      这一章的题（区间加 + 区间和）把那两端**同时**堵死了 ——
//      · 原数组：改一段要一格格加，O(len)；
//      · 前缀和：改一段之后整条 s[] 全废，O(n)。
//      **这就是为什么这道题非要线段树不可，而第 38 章那道题不用。**
//
// 复杂度 O(nm)。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<long long> a(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];

    string out;
    for (int q = 0; q < m; q++) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            long long x;
            cin >> x;
            for (int i = l; i <= r; i++) a[i] += x;
        } else {
            long long s = 0;
            for (int i = l; i <= r; i++) s += a[i];
            out += to_string(s);
            out += '\n';
        }
    }

    // ★ 末行：全部操作做完之后的整个数组（题面多问的那一句 —— 见 gen.cpp 开头那笔账）
    for (int i = 1; i <= n; i++) {
        out += to_string(a[i]);
        out += (i == n ? '\n' : ' ');
    }

    cout << out;
    return 0;
}

// ⚠ 这不是错误版本 —— 它的答案和正解**逐字节相同**，只是不用懒标记。
//
// 为什么它存在：
//   区间加不打标记的话，就只能老老实实一路递归到叶子，把每一个数真的改掉，
//   再一层层 pushup 回来。**答案完全正确，只是每次修改要碰 O(len) 个节点。**
//
//   ★ 于是它成了第 36 章立的那个「随机对拍的第四个盲区」在这一章的现场：
//     **只影响复杂度、不影响答案的写法，对拍原理上一个字都看不见。**
//     （第 36 章八种并查集写法、第 37 章 linear/sorted/堆、第 38 章 buildSlow —— 这是第四次。）
//   ⇒ 尺子只能换成「数节点」：count.cpp 数的是「访问了多少个树节点」。
//
//   ⚠ 而且它是这一章**唯一**能说清「懒标记到底省了什么」的东西：
//     正解和它的区别不在算法框架（同一棵树、同样的递归），
//     只在那一句 **「全覆盖就记一笔账走人」**。

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

const int MAXN = 100005;
long long sm[MAXN * 4];
long long a[MAXN];
int n, m;

inline void pushup(int o) { sm[o] = sm[o * 2] + sm[o * 2 + 1]; }

void build(int o, int l, int r) {
    if (l == r) { sm[o] = a[l]; return; }
    int mid = (l + r) / 2;
    build(o * 2, l, mid);
    build(o * 2 + 1, mid + 1, r);
    pushup(o);
}

/** ⚠ 没有标记可打，全覆盖也得继续往下走，一路走到叶子 */
void update(int o, int l, int r, int ql, int qr, long long x) {
    if (l == r) { sm[o] += x; return; }
    int mid = (l + r) / 2;
    if (ql <= mid) update(o * 2, l, mid, ql, qr, x);
    if (qr > mid) update(o * 2 + 1, mid + 1, r, ql, qr, x);
    pushup(o);
}

long long query(int o, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return sm[o];
    int mid = (l + r) / 2;
    long long s = 0;
    if (ql <= mid) s += query(o * 2, l, mid, ql, qr);
    if (qr > mid) s += query(o * 2 + 1, mid + 1, r, ql, qr);
    return s;
}

void flush(int o, int l, int r, string& out) {
    if (l == r) {
        out += to_string(sm[o]);
        out += (l == n ? '\n' : ' ');
        return;
    }
    int mid = (l + r) / 2;
    flush(o * 2, l, mid, out);
    flush(o * 2 + 1, mid + 1, r, out);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);

    string out;
    for (int q = 0; q < m; q++) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            long long x;
            cin >> x;
            update(1, 1, n, l, r, x);
        } else {
            out += to_string(query(1, 1, n, l, r));
            out += '\n';
        }
    }
    flush(1, 1, n, out);

    cout << out;
    return 0;
}

// 正解 —— 线段树 + 懒标记（区间加 / 区间和）
//
// ============ ★ 关键一步：懒标记 = 一句「欠着的修改」============
//
//   区间加 [l,r] += x 的时候，如果某个节点管的那一段**整个**落在 [l,r] 里面，
//   那么这一整段每个数都要加 x —— 可我们并不需要真的去改那一段里的每一个数：
//
//     · 这个节点自己的和，一句话就能算出来：sum[o] += x * (段长)；
//     · 至于它**底下**那些节点，先欠着 —— 在 lz[o] 上记一笔「我欠你们每人一个 x」。
//
//   ★ 所以 lz[o] 的含义要背得一字不差：
//     **「o 这个节点自己的 sum 已经算进去了，但 o 的两个儿子还不知道这件事。」**
//     （不是「这个区间要加 lz」，也不是「还没加」—— 差一个字，代码就写不对。）
//
//   于是区间加只在**边界上**留下 O(log n) 个「全覆盖」的节点，每个记一笔账就走人。
//   ⚠ 对照第 38 章：那道题只有单点改，一条 add 路径就完事，用不着欠账；
//     这一章一次要改一整段，**不欠账就只能一个个改，那就退回暴力了。**
//
// ============ ★★ 什么时候「必须」把账还了（pushdown）============
//
//   只有一种时候：**当你要往下走、要读儿子的值的时候。**
//   儿子的 sum 是「还没加过 lz[o]」的旧值，直接读就是错的。
//
//     · 全覆盖 → 直接用 sum[o]，**不用**下推（sum[o] 是对的）；
//     · 不相交 → 根本不往下走，**不用**下推；
//     · ★ 半覆盖 → 要递归进儿子，**必须先下推**。
//
//   ⇒ 一句话：**「懒」到不能再懒为止 —— 一直欠着，直到有人要看儿子。**
//   ⚠ 修改和查询**两边都要下推**（少写一处就是一个 bug，见 wrongPushQ / wrongPushU）。
//   ⚠ 下推之后 lz[o] 必须清零（账还完了要销账，见 wrongKeep）。
//
//   ★★ 但「必须下推」这句话是有条件的：条件是「**你要读儿子的值**」。
//     标记永久化（mark.cpp）换了个办法 —— 不下推，而是在**查询的路上**把沿途欠的账补回来，
//     答案 300 轮逐字节相同。所以它不是定律，是一个可以绕开的具体理由。
//
// ============ 结构（递归版）============
//
//   节点 o 管区间 [l,r]，左儿子 2o 管 [l,mid]，右儿子 2o+1 管 [mid+1,r]。
//   ⚠ 数组要开 **4n**：递归线段树的节点编号最坏能用到 4n（n 不是 2 的幂时树不满，
//     最下面一层会「错位」，2n 是不够的 —— 这是新手最常见的 RE）。
//
// 复杂度：建树 O(n)，每次操作 O(log n)。

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

const int MAXN = 100005;
long long sm[MAXN * 4];                       // sm[o]：o 这一段的和（★ 已经把 lz[o] 算进去了）
long long lz[MAXN * 4];                       // lz[o]：欠儿子们的那笔账（每人一个 lz[o]）
long long a[MAXN];
int n, m;

inline void pushup(int o) { sm[o] = sm[o * 2] + sm[o * 2 + 1]; }

/** 给节点 o（它管的段长是 len）整段加 x：自己的和当场算清，儿子的先欠着 */
inline void apply(int o, int len, long long x) {
    sm[o] += x * len;                         // ⚠ 忘了乘 len 是最常见的错（wrongLen.cpp）
    lz[o] += x;                               // ★ 是 +=，不是 =：欠了两笔账要叠起来
}

/** 把欠儿子的账还了，然后销账 */
inline void pushdown(int o, int l, int r) {
    if (!lz[o]) return;
    int mid = (l + r) / 2;
    apply(o * 2, mid - l + 1, lz[o]);
    apply(o * 2 + 1, r - mid, lz[o]);
    lz[o] = 0;                                // ⚠ 不清零就会重复还账（wrongKeep.cpp）
}

void build(int o, int l, int r) {
    lz[o] = 0;
    if (l == r) { sm[o] = a[l]; return; }
    int mid = (l + r) / 2;
    build(o * 2, l, mid);
    build(o * 2 + 1, mid + 1, r);
    pushup(o);
}

/** 区间加：[ql,qr] 每个数 += x */
void update(int o, int l, int r, int ql, int qr, long long x) {
    if (ql <= l && r <= qr) { apply(o, r - l + 1, x); return; }   // 全覆盖：记一笔账就走
    pushdown(o, l, r);                                           // ★ 要往下走了，先把账还了
    int mid = (l + r) / 2;
    if (ql <= mid) update(o * 2, l, mid, ql, qr, x);
    if (qr > mid) update(o * 2 + 1, mid + 1, r, ql, qr, x);      // ⚠ 两个 if，不是 if/else
    pushup(o);
}

/** 区间和：[ql,qr] */
long long query(int o, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return sm[o];                        // 全覆盖：sm[o] 本来就是对的
    pushdown(o, l, r);                                           // ★ 查询这一侧同样要下推
    int mid = (l + r) / 2;
    long long s = 0;
    if (ql <= mid) s += query(o * 2, l, mid, ql, qr);
    if (qr > mid) s += query(o * 2 + 1, mid + 1, r, ql, qr);
    return s;
}

/** ★ 末行要的是每一个 a[i]：把所有欠账一路推到叶子，账就全清了 */
void flush(int o, int l, int r, string& out) {
    if (l == r) {
        out += to_string(sm[o]);
        out += (l == n ? '\n' : ' ');
        return;
    }
    pushdown(o, l, r);
    int mid = (l + r) / 2;
    flush(o * 2, l, mid, out);
    flush(o * 2 + 1, mid + 1, r, out);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);

    string out;
    for (int q = 0; q < m; q++) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            long long x;
            cin >> x;
            update(1, 1, n, l, r, x);
        } else {
            out += to_string(query(1, 1, n, l, r));
            out += '\n';
        }
    }
    flush(1, 1, n, out);                       // ★ 末行：把欠着的账全部还清

    cout << out;
    return 0;
}

// 选讲 —— 标记永久化：**一次都不下推**，答案照样对。
//
// 为什么它存在：这一章从头到尾在讲「什么时候**必须**下推」，
// 而这份代码是那句话的**边界**：必须下推的真正理由只有一条 ——
//
//   > **你要去读儿子的 sum，而儿子的 sum 还不知道你欠它的那笔账。**
//
// 那么换个办法：**账一直挂在打标记的那个节点上（永久化），
// 谁要从上面走过去，谁就顺手把路过的账补进答案里。**
//
// ============ 两处约定（记清楚就不会写错）============
//
//   · sm[o] = o 这一段的**真实和**，但**不含它所有祖先的 tag**（自己的 tag 已经算进去了）；
//   · tg[o] = 「o 这一整段每个数都还要再加 tg[o]」，而且**永远不下发**。
//
//   区间加：沿途每个节点 sm[o] += x × (o 和 [ql,qr] 的交集长度)；
//           走到全覆盖的节点就 tg[o] += x，停。
//   区间查：一路往下带着 add =「沿途所有祖先 tg 之和」，
//           到全覆盖的节点返回 sm[o] + add × 段长。
//
// ============ ★ 它值钱在哪 ============
//
//   ① 它和正解 300 轮**逐字节相同** —— 又一个「对拍看不见」的现场，
//      而这次两份代码的**思路是不同的**（不是「同一个算法的两种写法」）。
//   ② ★ 它把「必须下推」从一条**定律**降回一个**具体的理由**：
//      理由消失（不再去读儿子的旧值），要求也就消失了。
//   ⚠ 但它有代价，正文里要写明：**只对「可交换、可叠加」的标记成立**
//      （区间加就是）。碰到区间赋值那种「后来的把先前的盖掉」的标记，
//      顺序一乱就错了 —— 那种情况老老实实下推。

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

const int MAXN = 100005;
long long sm[MAXN * 4];                       // 不含祖先 tg 的真实和
long long tg[MAXN * 4];                       // ★ 永久挂在这里，从不下发
long long a[MAXN];
int n, m;

void build(int o, int l, int r) {
    tg[o] = 0;
    if (l == r) { sm[o] = a[l]; return; }
    int mid = (l + r) / 2;
    build(o * 2, l, mid);
    build(o * 2 + 1, mid + 1, r);
    sm[o] = sm[o * 2] + sm[o * 2 + 1];
}

void update(int o, int l, int r, int ql, int qr, long long x) {
    sm[o] += x * (min(r, qr) - max(l, ql) + 1);              // 沿途每个节点都把真实贡献补上
    if (ql <= l && r <= qr) { tg[o] += x; return; }          // 全覆盖：账永久挂在这儿
    int mid = (l + r) / 2;
    if (ql <= mid) update(o * 2, l, mid, ql, qr, x);
    if (qr > mid) update(o * 2 + 1, mid + 1, r, ql, qr, x);
}

/** add = 从根到 o 的**所有祖先**的 tg 之和 */
long long query(int o, int l, int r, int ql, int qr, long long add) {
    if (ql <= l && r <= qr) return sm[o] + add * (r - l + 1);
    int mid = (l + r) / 2;
    long long s = 0, down = add + tg[o];
    if (ql <= mid) s += query(o * 2, l, mid, ql, qr, down);
    if (qr > mid) s += query(o * 2 + 1, mid + 1, r, ql, qr, down);
    return s;
}

void flush(int o, int l, int r, long long add, string& out) {
    if (l == r) {
        out += to_string(sm[o] + add);
        out += (l == n ? '\n' : ' ');
        return;
    }
    int mid = (l + r) / 2;
    long long down = add + tg[o];
    flush(o * 2, l, mid, down, out);
    flush(o * 2 + 1, mid + 1, r, down, out);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);

    string out;
    for (int q = 0; q < m; q++) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            long long x;
            cin >> x;
            update(1, 1, n, l, r, x);
        } else {
            out += to_string(query(1, 1, n, l, r, 0));
            out += '\n';
        }
    }
    flush(1, 1, n, 0, out);

    cout << out;
    return 0;
}

// ✗ 错误版本：**标记落到 sum 上时忘了乘区间长度**（sm[o] += x 而不是 x * len）
//
// 靠什么现形：只要有一次修改在**长度大于 1** 的节点上全覆盖就行 —— 什么数据都容易碰到。
//   ★ 所以它是这一章的**基线**：抓得住它，一点都不能说明生成器够狠
//     （第 38 章 wrongDir 的同款）。
// ⚠ 末行是**对的**：叶子的长度正好是 1，乘不乘一个样。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
long long sm[MAXN * 4];                       // sm[o]：o 这一段的和（★ 已经把 lz[o] 算进去了）
long long lz[MAXN * 4];                       // lz[o]：欠儿子们的那笔账（每人一个 lz[o]）
long long a[MAXN];
int n, m;

inline void pushup(int o) { sm[o] = sm[o * 2] + sm[o * 2 + 1]; }

/** 给节点 o（它管的段长是 len）整段加 x：自己的和当场算清，儿子的先欠着 */
inline void apply(int o, int len, long long x) {
    sm[o] += x;                               // ✗ 忘了乘 len：这一段有 len 个数，每人加 x
    lz[o] += x;                               // ★ 是 +=，不是 =：欠了两笔账要叠起来
}

/** 把欠儿子的账还了，然后销账 */
inline void pushdown(int o, int l, int r) {
    if (!lz[o]) return;
    int mid = (l + r) / 2;
    apply(o * 2, mid - l + 1, lz[o]);
    apply(o * 2 + 1, r - mid, lz[o]);
    lz[o] = 0;                                // ⚠ 不清零就会重复还账（wrongKeep.cpp）
}

void build(int o, int l, int r) {
    lz[o] = 0;
    if (l == r) { sm[o] = a[l]; return; }
    int mid = (l + r) / 2;
    build(o * 2, l, mid);
    build(o * 2 + 1, mid + 1, r);
    pushup(o);
}

/** 区间加：[ql,qr] 每个数 += x */
void update(int o, int l, int r, int ql, int qr, long long x) {
    if (ql <= l && r <= qr) { apply(o, r - l + 1, x); return; }   // 全覆盖：记一笔账就走
    pushdown(o, l, r);                                           // ★ 要往下走了，先把账还了
    int mid = (l + r) / 2;
    if (ql <= mid) update(o * 2, l, mid, ql, qr, x);
    if (qr > mid) update(o * 2 + 1, mid + 1, r, ql, qr, x);      // ⚠ 两个 if，不是 if/else
    pushup(o);
}

/** 区间和：[ql,qr] */
long long query(int o, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return sm[o];                        // 全覆盖：sm[o] 本来就是对的
    pushdown(o, l, r);                                           // ★ 查询这一侧同样要下推
    int mid = (l + r) / 2;
    long long s = 0;
    if (ql <= mid) s += query(o * 2, l, mid, ql, qr);
    if (qr > mid) s += query(o * 2 + 1, mid + 1, r, ql, qr);
    return s;
}

/** ★ 末行要的是每一个 a[i]：把所有欠账一路推到叶子，账就全清了 */
void flush(int o, int l, int r, string& out) {
    if (l == r) {
        out += to_string(sm[o]);
        out += (l == n ? '\n' : ' ');
        return;
    }
    pushdown(o, l, r);
    int mid = (l + r) / 2;
    flush(o * 2, l, mid, out);
    flush(o * 2 + 1, mid + 1, r, out);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);

    string out;
    for (int q = 0; q < m; q++) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            long long x;
            cin >> x;
            update(1, 1, n, l, r, x);
        } else {
            out += to_string(query(1, 1, n, l, r));
            out += '\n';
        }
    }
    flush(1, 1, n, out);                       // ★ 末行：把欠着的账全部还清

    cout << out;
    return 0;
}

// ✗ 错误版本：**查询的递归写成了 if / else**（跨过 mid 的区间只查了一半）
//
//   if (qr <= mid) 走左边; else 走右边;   ← 漏掉了「两边都要走」的那种情况
//
// 靠什么现形：★ **查询区间和节点区间的相对位置** —— 必须有查询**跨过某个 mid**。
//   ⇒ 这是「半覆盖那一支要够多」的那个旋钮，和值域、规模都没关系。
// ⚠ 末行是**对的**：flush 不走 query。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
long long sm[MAXN * 4];                       // sm[o]：o 这一段的和（★ 已经把 lz[o] 算进去了）
long long lz[MAXN * 4];                       // lz[o]：欠儿子们的那笔账（每人一个 lz[o]）
long long a[MAXN];
int n, m;

inline void pushup(int o) { sm[o] = sm[o * 2] + sm[o * 2 + 1]; }

/** 给节点 o（它管的段长是 len）整段加 x：自己的和当场算清，儿子的先欠着 */
inline void apply(int o, int len, long long x) {
    sm[o] += x * len;                         // ⚠ 忘了乘 len 是最常见的错（wrongLen.cpp）
    lz[o] += x;                               // ★ 是 +=，不是 =：欠了两笔账要叠起来
}

/** 把欠儿子的账还了，然后销账 */
inline void pushdown(int o, int l, int r) {
    if (!lz[o]) return;
    int mid = (l + r) / 2;
    apply(o * 2, mid - l + 1, lz[o]);
    apply(o * 2 + 1, r - mid, lz[o]);
    lz[o] = 0;                                // ⚠ 不清零就会重复还账（wrongKeep.cpp）
}

void build(int o, int l, int r) {
    lz[o] = 0;
    if (l == r) { sm[o] = a[l]; return; }
    int mid = (l + r) / 2;
    build(o * 2, l, mid);
    build(o * 2 + 1, mid + 1, r);
    pushup(o);
}

/** 区间加：[ql,qr] 每个数 += x */
void update(int o, int l, int r, int ql, int qr, long long x) {
    if (ql <= l && r <= qr) { apply(o, r - l + 1, x); return; }   // 全覆盖：记一笔账就走
    pushdown(o, l, r);                                           // ★ 要往下走了，先把账还了
    int mid = (l + r) / 2;
    if (ql <= mid) update(o * 2, l, mid, ql, qr, x);
    if (qr > mid) update(o * 2 + 1, mid + 1, r, ql, qr, x);      // ⚠ 两个 if，不是 if/else
    pushup(o);
}

/** 区间和：[ql,qr] */
long long query(int o, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return sm[o];                        // 全覆盖：sm[o] 本来就是对的
    pushdown(o, l, r);                                           // ★ 查询这一侧同样要下推
    int mid = (l + r) / 2;
    // ✗ 写成了 if / else：查询区间跨过 mid 时，右半边被整个吞掉了
    if (qr <= mid) return query(o * 2, l, mid, ql, qr);
    else return query(o * 2 + 1, mid + 1, r, ql, qr);
}

/** ★ 末行要的是每一个 a[i]：把所有欠账一路推到叶子，账就全清了 */
void flush(int o, int l, int r, string& out) {
    if (l == r) {
        out += to_string(sm[o]);
        out += (l == n ? '\n' : ' ');
        return;
    }
    pushdown(o, l, r);
    int mid = (l + r) / 2;
    flush(o * 2, l, mid, out);
    flush(o * 2 + 1, mid + 1, r, out);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);

    string out;
    for (int q = 0; q < m; q++) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            long long x;
            cin >> x;
            update(1, 1, n, l, r, x);
        } else {
            out += to_string(query(1, 1, n, l, r));
            out += '\n';
        }
    }
    flush(1, 1, n, out);                       // ★ 末行：把欠着的账全部还清

    cout << out;
    return 0;
}

// ✗ 错误版本：**修改完忘了 pushup**（儿子改了，父亲的 sm 还是旧的）
//
// 靠什么现形：一次**半覆盖**的修改（全覆盖那一支根本走不到 pushup），
//   之后有人来读那个父亲的 sm。
// ⚠ 末行是**对的**：叶子的值一点没坏，坏的只有内部节点的和。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
long long sm[MAXN * 4];                       // sm[o]：o 这一段的和（★ 已经把 lz[o] 算进去了）
long long lz[MAXN * 4];                       // lz[o]：欠儿子们的那笔账（每人一个 lz[o]）
long long a[MAXN];
int n, m;

inline void pushup(int o) { sm[o] = sm[o * 2] + sm[o * 2 + 1]; }

/** 给节点 o（它管的段长是 len）整段加 x：自己的和当场算清，儿子的先欠着 */
inline void apply(int o, int len, long long x) {
    sm[o] += x * len;                         // ⚠ 忘了乘 len 是最常见的错（wrongLen.cpp）
    lz[o] += x;                               // ★ 是 +=，不是 =：欠了两笔账要叠起来
}

/** 把欠儿子的账还了，然后销账 */
inline void pushdown(int o, int l, int r) {
    if (!lz[o]) return;
    int mid = (l + r) / 2;
    apply(o * 2, mid - l + 1, lz[o]);
    apply(o * 2 + 1, r - mid, lz[o]);
    lz[o] = 0;                                // ⚠ 不清零就会重复还账（wrongKeep.cpp）
}

void build(int o, int l, int r) {
    lz[o] = 0;
    if (l == r) { sm[o] = a[l]; return; }
    int mid = (l + r) / 2;
    build(o * 2, l, mid);
    build(o * 2 + 1, mid + 1, r);
    pushup(o);
}

/** 区间加：[ql,qr] 每个数 += x */
void update(int o, int l, int r, int ql, int qr, long long x) {
    if (ql <= l && r <= qr) { apply(o, r - l + 1, x); return; }   // 全覆盖：记一笔账就走
    pushdown(o, l, r);                                           // ★ 要往下走了，先把账还了
    int mid = (l + r) / 2;
    if (ql <= mid) update(o * 2, l, mid, ql, qr, x);
    if (qr > mid) update(o * 2 + 1, mid + 1, r, ql, qr, x);
    // ✗ 这里少了一句 pushup(o); —— 儿子改了，父亲的 sm 还停在改之前
}

/** 区间和：[ql,qr] */
long long query(int o, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return sm[o];                        // 全覆盖：sm[o] 本来就是对的
    pushdown(o, l, r);                                           // ★ 查询这一侧同样要下推
    int mid = (l + r) / 2;
    long long s = 0;
    if (ql <= mid) s += query(o * 2, l, mid, ql, qr);
    if (qr > mid) s += query(o * 2 + 1, mid + 1, r, ql, qr);
    return s;
}

/** ★ 末行要的是每一个 a[i]：把所有欠账一路推到叶子，账就全清了 */
void flush(int o, int l, int r, string& out) {
    if (l == r) {
        out += to_string(sm[o]);
        out += (l == n ? '\n' : ' ');
        return;
    }
    pushdown(o, l, r);
    int mid = (l + r) / 2;
    flush(o * 2, l, mid, out);
    flush(o * 2 + 1, mid + 1, r, out);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);

    string out;
    for (int q = 0; q < m; q++) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            long long x;
            cin >> x;
            update(1, 1, n, l, r, x);
        } else {
            out += to_string(query(1, 1, n, l, r));
            out += '\n';
        }
    }
    flush(1, 1, n, out);                       // ★ 末行：把欠着的账全部还清

    cout << out;
    return 0;
}

// ✗ 错误版本：**查询里忘了下推**（update 里那句还在，只漏了 query 里那一句）
//
// 靠什么现形：★ 一次区间加要在某个内部节点**停住**（半覆盖打了标记），
//   之后要有一次查询**钻进那个节点的子树里**（也是半覆盖）——
//   ⇒ 这是「两个操作之间的关系」，不是单个操作的形状。
//
// ⚠ 末行（整个数组）它是**对的**：flush 走的是另一条路，那里的 pushdown 没被删。
//   所以这个 bug 只在**查询那几行**上现形。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
long long sm[MAXN * 4];                       // sm[o]：o 这一段的和（★ 已经把 lz[o] 算进去了）
long long lz[MAXN * 4];                       // lz[o]：欠儿子们的那笔账（每人一个 lz[o]）
long long a[MAXN];
int n, m;

inline void pushup(int o) { sm[o] = sm[o * 2] + sm[o * 2 + 1]; }

/** 给节点 o（它管的段长是 len）整段加 x：自己的和当场算清，儿子的先欠着 */
inline void apply(int o, int len, long long x) {
    sm[o] += x * len;                         // ⚠ 忘了乘 len 是最常见的错（wrongLen.cpp）
    lz[o] += x;                               // ★ 是 +=，不是 =：欠了两笔账要叠起来
}

/** 把欠儿子的账还了，然后销账 */
inline void pushdown(int o, int l, int r) {
    if (!lz[o]) return;
    int mid = (l + r) / 2;
    apply(o * 2, mid - l + 1, lz[o]);
    apply(o * 2 + 1, r - mid, lz[o]);
    lz[o] = 0;                                // ⚠ 不清零就会重复还账（wrongKeep.cpp）
}

void build(int o, int l, int r) {
    lz[o] = 0;
    if (l == r) { sm[o] = a[l]; return; }
    int mid = (l + r) / 2;
    build(o * 2, l, mid);
    build(o * 2 + 1, mid + 1, r);
    pushup(o);
}

/** 区间加：[ql,qr] 每个数 += x */
void update(int o, int l, int r, int ql, int qr, long long x) {
    if (ql <= l && r <= qr) { apply(o, r - l + 1, x); return; }   // 全覆盖：记一笔账就走
    pushdown(o, l, r);                                           // ★ 要往下走了，先把账还了
    int mid = (l + r) / 2;
    if (ql <= mid) update(o * 2, l, mid, ql, qr, x);
    if (qr > mid) update(o * 2 + 1, mid + 1, r, ql, qr, x);      // ⚠ 两个 if，不是 if/else
    pushup(o);
}

/** 区间和：[ql,qr] */
long long query(int o, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return sm[o];
    // ✗ 这里少了一句 pushdown(o, l, r); —— 儿子的 sm 还是欠账前的旧值
    int mid = (l + r) / 2;
    long long s = 0;
    if (ql <= mid) s += query(o * 2, l, mid, ql, qr);
    if (qr > mid) s += query(o * 2 + 1, mid + 1, r, ql, qr);
    return s;
}

/** ★ 末行要的是每一个 a[i]：把所有欠账一路推到叶子，账就全清了 */
void flush(int o, int l, int r, string& out) {
    if (l == r) {
        out += to_string(sm[o]);
        out += (l == n ? '\n' : ' ');
        return;
    }
    pushdown(o, l, r);
    int mid = (l + r) / 2;
    flush(o * 2, l, mid, out);
    flush(o * 2 + 1, mid + 1, r, out);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);

    string out;
    for (int q = 0; q < m; q++) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            long long x;
            cin >> x;
            update(1, 1, n, l, r, x);
        } else {
            out += to_string(query(1, 1, n, l, r));
            out += '\n';
        }
    }
    flush(1, 1, n, out);                       // ★ 末行：把欠着的账全部还清

    cout << out;
    return 0;
}

// ✗ 错误版本：**修改里忘了下推**（query 里那句还在，只漏了 update 里那一句）
//
// 它错在哪，要说清楚（这里最容易想当然）：
//   区间加的标记是**可叠加**的，所以「儿子那边先欠着、我这边又欠一笔」本身并不矛盾。
//   真正错的是最后那句 **pushup**：sm[o] = sm[2o] + sm[2o+1] ——
//   ★ 两个儿子都还不知道 o 欠它们的那笔 lz[o]，于是 sm[o] 被这一句**改小了**。
//   ⇒ 「必须下推」的理由从来只有一条：**你要去读儿子的值。**
//     pushup 就是在读儿子的值。
//
// 靠什么现形：一次半覆盖的修改在某节点打上标记，之后**又一次修改**从它身上穿过去。
// ⚠ 末行（整个数组）它同样是**对的**：lz 本身没被改坏，flush 一路推到底还是对的。
//   坏掉的只有内部节点的 sm。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
long long sm[MAXN * 4];                       // sm[o]：o 这一段的和（★ 已经把 lz[o] 算进去了）
long long lz[MAXN * 4];                       // lz[o]：欠儿子们的那笔账（每人一个 lz[o]）
long long a[MAXN];
int n, m;

inline void pushup(int o) { sm[o] = sm[o * 2] + sm[o * 2 + 1]; }

/** 给节点 o（它管的段长是 len）整段加 x：自己的和当场算清，儿子的先欠着 */
inline void apply(int o, int len, long long x) {
    sm[o] += x * len;                         // ⚠ 忘了乘 len 是最常见的错（wrongLen.cpp）
    lz[o] += x;                               // ★ 是 +=，不是 =：欠了两笔账要叠起来
}

/** 把欠儿子的账还了，然后销账 */
inline void pushdown(int o, int l, int r) {
    if (!lz[o]) return;
    int mid = (l + r) / 2;
    apply(o * 2, mid - l + 1, lz[o]);
    apply(o * 2 + 1, r - mid, lz[o]);
    lz[o] = 0;                                // ⚠ 不清零就会重复还账（wrongKeep.cpp）
}

void build(int o, int l, int r) {
    lz[o] = 0;
    if (l == r) { sm[o] = a[l]; return; }
    int mid = (l + r) / 2;
    build(o * 2, l, mid);
    build(o * 2 + 1, mid + 1, r);
    pushup(o);
}

/** 区间加：[ql,qr] 每个数 += x */
void update(int o, int l, int r, int ql, int qr, long long x) {
    if (ql <= l && r <= qr) { apply(o, r - l + 1, x); return; }   // 全覆盖：记一笔账就走
    // ✗ 这里少了一句 pushdown(o, l, r); —— 下面那句 pushup 会读到儿子的旧值
    int mid = (l + r) / 2;
    if (ql <= mid) update(o * 2, l, mid, ql, qr, x);
    if (qr > mid) update(o * 2 + 1, mid + 1, r, ql, qr, x);      // ⚠ 两个 if，不是 if/else
    pushup(o);
}

/** 区间和：[ql,qr] */
long long query(int o, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return sm[o];                        // 全覆盖：sm[o] 本来就是对的
    pushdown(o, l, r);                                           // ★ 查询这一侧同样要下推
    int mid = (l + r) / 2;
    long long s = 0;
    if (ql <= mid) s += query(o * 2, l, mid, ql, qr);
    if (qr > mid) s += query(o * 2 + 1, mid + 1, r, ql, qr);
    return s;
}

/** ★ 末行要的是每一个 a[i]：把所有欠账一路推到叶子，账就全清了 */
void flush(int o, int l, int r, string& out) {
    if (l == r) {
        out += to_string(sm[o]);
        out += (l == n ? '\n' : ' ');
        return;
    }
    pushdown(o, l, r);
    int mid = (l + r) / 2;
    flush(o * 2, l, mid, out);
    flush(o * 2 + 1, mid + 1, r, out);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);

    string out;
    for (int q = 0; q < m; q++) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            long long x;
            cin >> x;
            update(1, 1, n, l, r, x);
        } else {
            out += to_string(query(1, 1, n, l, r));
            out += '\n';
        }
    }
    flush(1, 1, n, out);                       // ★ 末行：把欠着的账全部还清

    cout << out;
    return 0;
}

// ✗ 错误版本：**下推之后忘了销账**（lz[o] 没清零）
//
// 于是同一笔账会被**反复下发**：每有一个人从 o 身上穿过去，儿子就再被加一次。
//
// 靠什么现形：★ 同一个节点要被**下推两次**（也就是被穿过两次）——
//   ⇒ 又是「两个操作之间的关系」，而且它比 wrongPushQ 更贪心：要三件事按顺序发生
//     （打标记 → 穿过去一次 → 再穿过去一次）。
// ★ 末行会跟着一起错：flush 是最后一次穿过，重复的账全落到叶子上。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
long long sm[MAXN * 4];                       // sm[o]：o 这一段的和（★ 已经把 lz[o] 算进去了）
long long lz[MAXN * 4];                       // lz[o]：欠儿子们的那笔账（每人一个 lz[o]）
long long a[MAXN];
int n, m;

inline void pushup(int o) { sm[o] = sm[o * 2] + sm[o * 2 + 1]; }

/** 给节点 o（它管的段长是 len）整段加 x：自己的和当场算清，儿子的先欠着 */
inline void apply(int o, int len, long long x) {
    sm[o] += x * len;                         // ⚠ 忘了乘 len 是最常见的错（wrongLen.cpp）
    lz[o] += x;                               // ★ 是 +=，不是 =：欠了两笔账要叠起来
}

/** 把欠儿子的账还了，然后销账 */
inline void pushdown(int o, int l, int r) {
    if (!lz[o]) return;
    int mid = (l + r) / 2;
    apply(o * 2, mid - l + 1, lz[o]);
    apply(o * 2 + 1, r - mid, lz[o]);
    // ✗ 这里少了一句 lz[o] = 0; —— 账还了却不销，下次路过再还一遍
}

void build(int o, int l, int r) {
    lz[o] = 0;
    if (l == r) { sm[o] = a[l]; return; }
    int mid = (l + r) / 2;
    build(o * 2, l, mid);
    build(o * 2 + 1, mid + 1, r);
    pushup(o);
}

/** 区间加：[ql,qr] 每个数 += x */
void update(int o, int l, int r, int ql, int qr, long long x) {
    if (ql <= l && r <= qr) { apply(o, r - l + 1, x); return; }   // 全覆盖：记一笔账就走
    pushdown(o, l, r);                                           // ★ 要往下走了，先把账还了
    int mid = (l + r) / 2;
    if (ql <= mid) update(o * 2, l, mid, ql, qr, x);
    if (qr > mid) update(o * 2 + 1, mid + 1, r, ql, qr, x);      // ⚠ 两个 if，不是 if/else
    pushup(o);
}

/** 区间和：[ql,qr] */
long long query(int o, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return sm[o];                        // 全覆盖：sm[o] 本来就是对的
    pushdown(o, l, r);                                           // ★ 查询这一侧同样要下推
    int mid = (l + r) / 2;
    long long s = 0;
    if (ql <= mid) s += query(o * 2, l, mid, ql, qr);
    if (qr > mid) s += query(o * 2 + 1, mid + 1, r, ql, qr);
    return s;
}

/** ★ 末行要的是每一个 a[i]：把所有欠账一路推到叶子，账就全清了 */
void flush(int o, int l, int r, string& out) {
    if (l == r) {
        out += to_string(sm[o]);
        out += (l == n ? '\n' : ' ');
        return;
    }
    pushdown(o, l, r);
    int mid = (l + r) / 2;
    flush(o * 2, l, mid, out);
    flush(o * 2 + 1, mid + 1, r, out);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);

    string out;
    for (int q = 0; q < m; q++) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            long long x;
            cin >> x;
            update(1, 1, n, l, r, x);
        } else {
            out += to_string(query(1, 1, n, l, r));
            out += '\n';
        }
    }
    flush(1, 1, n, out);                       // ★ 末行：把欠着的账全部还清

    cout << out;
    return 0;
}

// ✗ 错误版本：**打标记时写成 lz[o] = x，而不是 lz[o] += x**（两笔账没叠起来）
//
// 靠什么现形：★ 同一个节点要被**连着两次全覆盖**，而且中间**没有人来下推**。
//   ⇒ 「两个操作之间的关系」里最苛刻的一个：不但要两次操作打在同一个节点上，
//     还要求这两次之间没有第三个操作从那儿穿过去（穿过去就把第一笔账下发了，也就叠不上了）。
// ★ 末行会跟着错：被吞掉的那笔账永远补不回来。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
long long sm[MAXN * 4];                       // sm[o]：o 这一段的和（★ 已经把 lz[o] 算进去了）
long long lz[MAXN * 4];                       // lz[o]：欠儿子们的那笔账（每人一个 lz[o]）
long long a[MAXN];
int n, m;

inline void pushup(int o) { sm[o] = sm[o * 2] + sm[o * 2 + 1]; }

/** 给节点 o（它管的段长是 len）整段加 x：自己的和当场算清，儿子的先欠着 */
inline void apply(int o, int len, long long x) {
    sm[o] += x * len;                         // ⚠ 忘了乘 len 是最常见的错（wrongLen.cpp）
    lz[o] = x;                                // ✗ 写成了 =：先前欠的那笔账被直接抹掉了
}

/** 把欠儿子的账还了，然后销账 */
inline void pushdown(int o, int l, int r) {
    if (!lz[o]) return;
    int mid = (l + r) / 2;
    apply(o * 2, mid - l + 1, lz[o]);
    apply(o * 2 + 1, r - mid, lz[o]);
    lz[o] = 0;                                // ⚠ 不清零就会重复还账（wrongKeep.cpp）
}

void build(int o, int l, int r) {
    lz[o] = 0;
    if (l == r) { sm[o] = a[l]; return; }
    int mid = (l + r) / 2;
    build(o * 2, l, mid);
    build(o * 2 + 1, mid + 1, r);
    pushup(o);
}

/** 区间加：[ql,qr] 每个数 += x */
void update(int o, int l, int r, int ql, int qr, long long x) {
    if (ql <= l && r <= qr) { apply(o, r - l + 1, x); return; }   // 全覆盖：记一笔账就走
    pushdown(o, l, r);                                           // ★ 要往下走了，先把账还了
    int mid = (l + r) / 2;
    if (ql <= mid) update(o * 2, l, mid, ql, qr, x);
    if (qr > mid) update(o * 2 + 1, mid + 1, r, ql, qr, x);      // ⚠ 两个 if，不是 if/else
    pushup(o);
}

/** 区间和：[ql,qr] */
long long query(int o, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return sm[o];                        // 全覆盖：sm[o] 本来就是对的
    pushdown(o, l, r);                                           // ★ 查询这一侧同样要下推
    int mid = (l + r) / 2;
    long long s = 0;
    if (ql <= mid) s += query(o * 2, l, mid, ql, qr);
    if (qr > mid) s += query(o * 2 + 1, mid + 1, r, ql, qr);
    return s;
}

/** ★ 末行要的是每一个 a[i]：把所有欠账一路推到叶子，账就全清了 */
void flush(int o, int l, int r, string& out) {
    if (l == r) {
        out += to_string(sm[o]);
        out += (l == n ? '\n' : ' ');
        return;
    }
    pushdown(o, l, r);
    int mid = (l + r) / 2;
    flush(o * 2, l, mid, out);
    flush(o * 2 + 1, mid + 1, r, out);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);

    string out;
    for (int q = 0; q < m; q++) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            long long x;
            cin >> x;
            update(1, 1, n, l, r, x);
        } else {
            out += to_string(query(1, 1, n, l, r));
            out += '\n';
        }
    }
    flush(1, 1, n, out);                       // ★ 末行：把欠着的账全部还清

    cout << out;
    return 0;
}

// 正解 —— 线段树 + 懒标记（区间加 / 区间和）
//
// ============ ★ 关键一步：懒标记 = 一句「欠着的修改」============
//
//   区间加 [l,r] += x 的时候，如果某个节点管的那一段**整个**落在 [l,r] 里面，
//   那么这一整段每个数都要加 x —— 可我们并不需要真的去改那一段里的每一个数：
//
//     · 这个节点自己的和，一句话就能算出来：sum[o] += x * (段长)；
//     · 至于它**底下**那些节点，先欠着 —— 在 lz[o] 上记一笔「我欠你们每人一个 x」。
//
//   ★ 所以 lz[o] 的含义要背得一字不差：
//     **「o 这个节点自己的 sum 已经算进去了，但 o 的两个儿子还不知道这件事。」**
//     （不是「这个区间要加 lz」，也不是「还没加」—— 差一个字，代码就写不对。）
//
//   于是区间加只在**边界上**留下 O(log n) 个「全覆盖」的节点，每个记一笔账就走人。
//   ⚠ 对照第 38 章：那道题只有单点改，一条 add 路径就完事，用不着欠账；
//     这一章一次要改一整段，**不欠账就只能一个个改，那就退回暴力了。**
//
// ============ ★★ 什么时候「必须」把账还了（pushdown）============
//
//   只有一种时候：**当你要往下走、要读儿子的值的时候。**
//   儿子的 sum 是「还没加过 lz[o]」的旧值，直接读就是错的。
//
//     · 全覆盖 → 直接用 sum[o]，**不用**下推（sum[o] 是对的）；
//     · 不相交 → 根本不往下走，**不用**下推；
//     · ★ 半覆盖 → 要递归进儿子，**必须先下推**。
//
//   ⇒ 一句话：**「懒」到不能再懒为止 —— 一直欠着，直到有人要看儿子。**
//   ⚠ 修改和查询**两边都要下推**（少写一处就是一个 bug，见 wrongPushQ / wrongPushU）。
//   ⚠ 下推之后 lz[o] 必须清零（账还完了要销账，见 wrongKeep）。
//
//   ★★ 但「必须下推」这句话是有条件的：条件是「**你要读儿子的值**」。
//     标记永久化（mark.cpp）换了个办法 —— 不下推，而是在**查询的路上**把沿途欠的账补回来，
//     答案 300 轮逐字节相同。所以它不是定律，是一个可以绕开的具体理由。
//
// ============ 结构（递归版）============
//
//   节点 o 管区间 [l,r]，左儿子 2o 管 [l,mid]，右儿子 2o+1 管 [mid+1,r]。
//   ⚠ 数组要开 **4n**：递归线段树的节点编号最坏能用到 4n（n 不是 2 的幂时树不满，
//     最下面一层会「错位」，2n 是不够的 —— 这是新手最常见的 RE）。
//
// 复杂度：建树 O(n)，每次操作 O(log n)。

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

const int MAXN = 100005;
long long sm[MAXN * 4];                       // sm[o]：o 这一段的和（★ 已经把 lz[o] 算进去了）
long long lz[MAXN * 4];                       // lz[o]：欠儿子们的那笔账（每人一个 lz[o]）
long long a[MAXN];
int n, m;

inline void pushup(int o) { sm[o] = sm[o * 2] + sm[o * 2 + 1]; }

/** 给节点 o（它管的段长是 len）整段加 x：自己的和当场算清，儿子的先欠着 */
inline void apply(int o, int len, long long x) {
    sm[o] += x * len;                         // ⚠ 忘了乘 len 是最常见的错（wrongLen.cpp）
    lz[o] += x;                               // ★ 是 +=，不是 =：欠了两笔账要叠起来
}

/** 把欠儿子的账还了，然后销账 */
inline void pushdown(int o, int l, int r) {
    if (!lz[o]) return;
    int mid = (l + r) / 2;
    apply(o * 2, mid - l + 1, lz[o]);
    apply(o * 2 + 1, r - mid, lz[o]);
    lz[o] = 0;                                // ⚠ 不清零就会重复还账（wrongKeep.cpp）
}

void build(int o, int l, int r) {
    lz[o] = 0;
    if (l == r) { sm[o] = a[l]; return; }
    int mid = (l + r) / 2;
    build(o * 2, l, mid);
    build(o * 2 + 1, mid + 1, r);
    pushup(o);
}

/** 区间加：[ql,qr] 每个数 += x */
void update(int o, int l, int r, int ql, int qr, long long x) {
    if (ql <= l && r <= qr) { apply(o, r - l + 1, x); return; }   // 全覆盖：记一笔账就走
    pushdown(o, l, r);                                           // ★ 要往下走了，先把账还了
    int mid = (l + r) / 2;
    if (ql <= mid) update(o * 2, l, mid, ql, qr, x);
    if (qr > mid) update(o * 2 + 1, mid + 1, r, ql, qr, x);      // ⚠ 两个 if，不是 if/else
    pushup(o);
}

/** 区间和：[ql,qr] */
long long query(int o, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return sm[o];                        // 全覆盖：sm[o] 本来就是对的
    pushdown(o, l, r);                                           // ★ 查询这一侧同样要下推
    int mid = (l + r) / 2;
    long long s = 0;
    if (ql <= mid) s += query(o * 2, l, mid, ql, qr);
    if (qr > mid) s += query(o * 2 + 1, mid + 1, r, ql, qr);
    return s;
}

/** ★ 末行要的是每一个 a[i]：把所有欠账一路推到叶子，账就全清了 */
void flush(int o, int l, int r, string& out) {
    if (l == r) {
        out += to_string(sm[o]);
        out += (l == n ? '\n' : ' ');
        return;
    }
    pushdown(o, l, r);
    int mid = (l + r) / 2;
    flush(o * 2, l, mid, out);
    flush(o * 2 + 1, mid + 1, r, out);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);

    string out;
    for (int q = 0; q < m; q++) {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1) {
            long long x;
            cin >> x;
            update(1, 1, n, l, r, x);
        } else {
            out += to_string(query(1, 1, n, l, r));
            out += '\n';
        }
    }
    flush(1, 1, n, out);                       // ★ 末行：把欠着的账全部还清

    cout << out;
    return 0;
}