【例题4】区间修改区间查询

题目描述

这是一道模板题。

给定数列$a_1$,$a_2$,$\ldots$,$a_n$，你需要依次进行$q$个操作，操作有两类：

• $1$ $l$ $r$ $x$：给定$l$,$r$,$x$，对于所有$i \in [l,r]$，将$a_i$加上$x$（换言之，将$a_l$,$a_{l+1}$,$\ldots$,$a_r$分别加上$x$）；
• $2$ $l$ $r$：给定$l$,$r$，求$\sum_{i=l}^{r}a_i$的值（换言之，求$a_l+a_{l+1}+\cdots+a_r$的值）。

输入格式

第一行包含$2$个正整数$n$,$q$，表示数列长度和询问个数。保证$1 \leq n,q \leq 10^{6}$。

第二行$n$个整数$a_1$,$a_2$,$\ldots$,$a_n$，表示初始数列。保证$|a_i| \leq 10^{6}$。

接下来$q$行，每行一个操作，为以下两种之一：

• $1$ $l$ $r$ $x$：对于所有$i \in [l,r]$，将$a_i$加上$x$；
• $2$ $l$ $r$：输出$\sum_{i=l}^{r}a_i$的值。

保证$1 \leq l \leq r \leq n$，$|x| \leq 10^{6}$。

输出格式

对于每个$2$ $l$ $r$操作，输出一行，每行有一个整数，表示所求的结果。

数据范围与提示

对于所有数据，$1 \leq n,q \leq 10^{6}$，$|a_i| \leq 10^{6}$，$1 \leq l \leq r \leq n$，$|x| \leq 10^{6}$。

样例

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