数列操作与查询模板题

一、题目描述

给定一个数列$a[1], a[2], \cdots, a[n]$，需要依次执行$q$个操作。操作有两类：

1. 操作类型为 1 l r x：对于区间$[l, r]$内的所有$i$，将$a[i]$的值增加$x$，即$a[l], a[l + 1], \cdots, a[r]$分别加上$x$。
2. 操作类型为 2 l r：计算并返回区间$[l, r]$内数列元素的和，即$a[l] + a[l + 1] + \cdots + a[r]$的值。

二、输入格式

1. 第一行：两个正整数$n$和$q$，分别表示数列长度和询问个数，保证$1 \leq n, q \leq 10^6$。
2. 第二行：$n$个整数$a[1], a[2], \cdots, a[n]$，表示初始数列，保证$\vert a[i] \vert \leq 10^6$ 。
3. 接下来$q$行：每行一个操作，格式为 1 l r x 或 2 l r，保证$1 \leq l \leq r \leq n$，$\vert x \vert \leq 10^6$ 。

三、输出格式

对于每个类型为 2 l r 的操作，输出一行，包含一个整数，表示区间$[l, r]$内数列元素的和。

四、样例

输入

5 10
2 6 6 1 1
2 1 4
1 2 5 10
2 1 3
2 2 3
1 2 2 8
1 2 3 7
1 4 4 10
2 1 2
1 4 5 6
2 3 4

输出

15
34
32
33
50

五、数据范围与提示

所有数据均满足$1 \leq n, q \leq 10^6$，$\vert a[i] \vert \leq 10^6$，$1 \leq l \leq r \leq n$，$\vert x \vert \leq 10^6$ 。