时间限制： 1.5 秒

空间限制： 512 MB

题目描述

给定长度为 $n$ 的数列 $a_1,\cdots,a_n$，你需要依次进行 $q$ 次操作，操作分两类：

• $1~l~r~x$：给定 $l,r,x$，对于所有的 $i\in [l,r]$，将 $a_i$ 加上 $x$；
• $2~l~r$：给定 $l,r$，求 $\sum\limits_{i=l}^r a_i$ 的值。

即最为基础的“区间加/区间和”操作。

输入格式

从标准输入读入数据。

第一行包含两个正整数 $n,q$，表示数列长度和操作个数。

第二行 $n$ 个整数 $a_1,\cdots,a_n$，表示初始序列。

接下来 $q$ 行，每行一个操作，格式见【题目描述】。

输出格式

输出到标准输出。

对于每次操作 2，输出一行一个整数，表示对应操作的区间查询结果。

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\le n,q\le 10^6,-10^6\le a_i,x\le 10^6,1\le l\le r\le n$。

提示

邓俊辉《数据结构》课件 7-B 线段树

不过遗憾的是，邓教授课件当中的内容非常脱离实际应用。推荐搭配结合 OI-Wiki 线段树基础 进行学习。

这里只说一点课件上关于空间复杂度描述与实际使用的歧义。

课件上提到的线段树空间复杂度之所以 $O(n\log n)$，是因为课件上的区间查询并非查询一个区间的和，而是要把区间内所有元素都具体地输出出来。因此对于一个长度为 $n$ 的区间，本题中只需要在线段树节点上维护这 $n$ 个元素的加和即可（空间复杂度 $O(1)$），而在课件上需要将 $n$ 个元素逐一排列在节点上（空间复杂度 $O(n)$）。在本题这样的实际应用中，空间复杂度还是 $O(n)$ 的。

线段树在清华 826 考研初试中大概率是不会考的，但是也是准备后续复试机试以及算法竞赛的基础内容，有余力的话还是推荐做一个简单了解即可。

此外，本题还可以使用树状数组通过。

来源

LOJ 132