分块区间操作与求和问题

1. 题目描述

给定一个长度为 $n$ 的整数数组 $a$（下标从 1 开始），需要支持以下两种操作：

• 当操作类型为 0 时，表示修改操作。给定三个整数 $l$，$r$ 和 $x$，将区间 $[l, r]$ 内的所有值增加 $x$。
• 当操作类型为 1 时，表示查询操作。给定两个整数 $l$ 和 $r$，计算数组中 $a_l, a_{l + 1}, \cdots, a_r$ 的和。

请使用分块思想实现对这些操作的高效处理。

2. 输入

2.1 输入格式

• 第一行：两个整数 $n$ 和 $m$（$1 \leq n, m \leq 10^5$），分别表示数组长度和操作数量。
• 第二行：$n$ 个整数 $a_1, a_2, \cdots, a_n$（$-10^9 \leq a_i \leq 10^9$），表示初始数组。
• 接下来 $m$ 行：每行四个整数 $op$，$l$，$r$，$x$。其中 $op$ 取值为 0 或 1，$1 \leq l \leq r \leq n$，$-10^9 \leq x \leq 10^9$。当 $op = 0$ 时，代表修改操作，$l$ 和 $r$ 表示区间的左右边界，$x$ 表示要增加的值；当 $op = 1$ 时，代表查询操作，$l$ 和 $r$ 分别表示查询区间的左、右边界。

2.2 输入样例

5 5
1 2 3 4 5
1 1 3
0 2 4 3
1 2 4
0 1 5 2
1 1 5

3. 输出

3.1 输出格式

对于每个查询操作（即 $op = 1$ 时），输出一个整数，表示对应区间的和，每个结果占一行。

3.2 输出样例

6
18
34

4. 数据范围

• $1 \leq n \leq 10^5$。
• $1 \leq m \leq 10^5$。
• $-10^9 \leq a_i \leq 10^9$。
• $op \in \{0, 1\}$。
• $1 \leq l \leq r \leq n$。
• $-10^9 \leq x \leq 10^9$。