题目：树状数组3 ：区间修改，区间查询

题目描述

给定长度为 $n$ 的数列 $a[1], a[2], \dots, a[n]$，需依次处理 $q$ 个操作，操作分为两类：

1. 区间更新：1 l r x → 将区间 $[l, r]$ 内的每个元素 $a[i]$ 加上 $x$（即 $a[l], a[l+1], \dots, a[r]$ 分别加 $x$）；
2. 区间查询：2 l r → 求区间和 $\sum_{i=l}^r a[i]$（即 $a[l] + a[l+1] + \dots + a[r]$ 的值）。

输入格式

• 第一行：两个整数 $n, q$（$1 \leq n, q \leq 10^6$），表示数列长度和操作数；
• 第二行：$n$ 个整数 $a[1], a[2], \dots, a[n]$（初始数列，$|a[i]| \leq 10^6$）；
• 接下来 $q$ 行：每行一个操作，格式为 1 l r x 或 2 l r（保证 $1 \leq l \leq r \leq n$，$|x| \leq 10^6$）。

输出格式

对于每个 区间查询操作（类型2），输出一行，为对应区间的和。

样例

输入：

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

输出：

23
40
36
91
47