题目：
给定一个长度为 N 的数组 a，其初值分别为a1,a2,...,aN。
现有 Q 个操作，操作有以下两种：
1 l r k，将区间 al,al+1,...ar 的值加上 k。2 l r，求区间al,al+1,...,ar 的和为多少。输入描述
输入第 1 行包含两个正整数 N,Q，分别表示数组 a 的长度和操作的个数。
第 2 行包含 N 个非负整数 a1,a2,...,aN，表示数组 a 元素的初值。
第 3∼Q−2 行每行表示一共操作，格式为以下两种之一：
1 l r x2 l r其含义如题所述。
1≤N,Q≤10^5，1≤l≤r≤N，−10^9≤k,ai≤10^9。
输出描述
输出共 Q 行，每行包含一个整数，表示相应查询的答案。
输入输出样例
示例 1
输入
1. 5 5 2. 1 2 3 4 3. 2 1 2 4. 1 2 3 1 5. 2 1 3 6. 1 1 5 1 7. 2 1 5
输出
1. 3 2. 8 3. 22
运行限制
- 最大运行时间：2s
- 最大运行内存: 256M
思路
区间和查询
我们可以通过线段树的数据结构查询一个区间的最大值，如上图所示，是一棵表示区间和的线段树，它用于查询{1, 4, 5, 8, 6, 2, 3, 9, 10, 71,4,5,8,6,2,3,9,10,7} 区间和，每个结点上圆圈内的数字是这棵子树的和。例如查区间 [4, 9][4,9] 的和，递归查询到区间 [4, 5]、[6, 8]、[9, 9][4,5]、[6,8]、[9,9]，见图中画横线的线段，得 sum{14, 14, 10} = 38。
查询递归到某个结点 p（p表示的区间是 [pl, pr]）时，有 2 种情况：
1.[L,R] 完全覆盖了 [pl, pr] ，即 L ≤ pl ≤ pr ≤ R，说明[l,r]在[x,y]树结构的上面，此时p就是区间和直接返回 p 的值即可。
2.[L,R] 与 [pl, pr] 部分重叠，分别搜左右子结点。
- L < pr，继续递归左子结点，例如查询区间 [4,9]，与第 2 个结点 [1,5] 有重叠，因为 4 < 5，进入递归把[4,5]的区间和返回。
- R > pl，继续递归右子结点，例如 [4, 9] 与第 3 个结点 [6,10] 有重叠，因为9>6。进入递归把[6,8],[9,9]的区间和返回
区间和的查询将主要体现在代码中的query()函数中。
区间修改和懒惰标记
我们可以通过在每一个结点中定义一个tag[i]来统一记录这个区间的修改，而不必一个个的修改区间内每个元素。这个方法就是”lazy-tag“。
当修改的是一个线段区间时，就只对这个线段区间进行整体上的修改，其内部每个元素的内容先不做修改，只有当这个线段区间的一致性被破坏时，才把变化值传递给下一层的子区间。这样每次区间修改的复杂度是O(logn)的，一共 m 次操作，总复杂度是 O(mlogn)的（区间 i的 lazy操作，我们用 tag[i]记录）。
比如下图：
[4,9] 区间内的每个元素加 3，执行步骤是：
- 左子树递归到结点 5，即区间 [4,5]，完全包含在 [4,9] 内，打标记tag[5]=3，更新 tree[5] 为 20，不再继续深入；
- 左子树递归返回，更新 tree[2]为 30；
- 右子树递归到结点 6，即区间 [6,8]，完全包含在 [4, 9][4,9] 内，打标记tag[6]=3，更新 tree[6] 为 23。
- 右子树递归到结点 14，即区间 [9, 9]，打标记 tag[14]=3，更新tree[14]=13；
- 右子树递归返回，更新 tree[7]=20；继续返回，更新 tree[3]=43；
- 返回到根结点，更新 tree[1]=73。
但我们要注意到一点， 如果发生了多次修改，即同一个结点上的 tagtag 发生多次修改，会导致冲突吧。例如做 2 次区间修改，一次是 [4,9]，一次是[5,8]，它们都会影响 5:[4,5] 这个结点。第一次修改 [4,9] 覆盖了结点 5，用 tag[5] 做了记录；而第二次修改 [5,8] 不能覆盖结点 5，需要再向下搜到结点 11:[5,5] ，从而破坏了 tag[5]，此时原 tag[5] 记录的区间统一修改就不得不往它的子结点传递和执行了，传递后 tag[5] 失去了用途，应当清空为0。为此我们设计down()函数，用于处理tag冲突问题。
我们下面介绍4个函数：
1.build（）
建树，通过递归，先到叶子节点，再从下往上建树
2.down()
把tag传给子树，给左右子树的tag[]赋值，并且更新子树结点的值,用来解决tag冲突问题。
3.modify()
- 如果 tree[p]tree[p] 这棵子树完全被包含在需要修改的区间 [L, R][L,R] 中，那么只需要对根 tree[p]tree[p] 打上标记即可，不用修改子结点。
- 如果不能覆盖，需要解决多次修改的冲突问题，用
push_down()实现。
然后后面就是二分了。二分之后再把修改值传回上层。
4.query（）
查询区间和，见上文
注意树的存储空间
树的存储空间要4N，因为假设有一棵处理 n 个元素（叶子结点有 n 个）的线段树，且它的最后一层只有 1 个叶子，其他层都是满的；如果用满二叉树表示，它的结点总数是：最后一层有 2n 个结点（其中 2n−1 个都浪费了没用到），而前面所有的层有 2n 个结点，加起来共 4n 个结点。
代码
1. N=100001 2. [n,m]=list(map(int,input().split())) 3. num=list(map(int,input().split())) 4. class SegTree(): 5. def __init__(self): 6. self.sum=0 7. self.tag=0 8. tr=[SegTree() for i in range(N*4)] 9. #通过递归，先到叶子节点，再从下往上建树 10. def build(p,l,r): 11. if(l==r): 12. #最底层的叶子，赋值 13. tr[p].sum=num[l-1] 14. return 15. global segs 16. mid=(l+r)>>1 17. build(p<<1,l,mid) 18. build(p<<1|1,mid+1,r) 19. tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum 20. return 21. 22. #把tag传给子树，并且更新子树的值 23. #用来解决tag冲突问题 24. def down(p,s): 25. #将tag传给左子树 26. tr[p<<1].sum+=tr[p].tag*(s-(s>>1)) 27. tr[p<<1].tag+=tr[p].tag 28. #将tag传给右子树 29. tr[p<<1|1].sum+=tr[p].tag*(s>>1) 30. tr[p<<1|1].tag+=tr[p].tag 31. tr[p].tag=0 32. return 33. 34. #区间修改，把x,y之内的元素加上z 35. def modify(x,y,z,p,l,r): 36. #如果l,r在【x,y】中 37. if(x<=l)&(r<=y): 38. #给结点p打标记，并且更新结点的值 39. tr[p].sum+=z*(r-l+1) 40. tr[p].tag+=z 41. #如果完全覆盖，直接返回这个结点 42. #它的子树不用再深入 43. return 44. #如果不在，且tr之前被打过标记 45. #把tag传给子树 46. if(tr[p].tag!=0): 47. down(p,r-l+1) 48. mid=(l+r)>>1 49. #递归左子树 50. if(x<=mid): 51. modify(x,y,z,p<<1,l,mid) 52. #递归右子树 53. if(y>mid): 54. modify(x,y,z,p<<1|1,mid+1,r) 55. #更新树上的结点 56. tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum 57. return 58. 59. #查询区间的和 60. def query(x,y,p,l,r): 61. #完全覆盖，直接返回 62. #[l,r]在[x,y]树结构的上面，此时p就是区间和 63. if(x<=l)&(r<=y): 64. return tr[p].sum 65. #不能覆盖，递归子树 66. if(tr[p].tag!=0): 67. down(p,r-l+1) 68. mid=(l+r)>>1 69. res=0 70. #左节点有重合 71. if(x<=mid): 72. res+=query(x,y,p<<1,l,mid) 73. #右节点有重合 74. if(y>mid): 75. res+=query(x,y,p<<1|1,mid+1,r) 76. return res 77. build(1,1,n) 78. while(m>0): 79. m-=1 80. op=list(map(int,input().split())) 81. if(op[0]==1): 82. modify(op[1],op[2],op[3],1,1,n) 83. else: 84. print(query(op[1],op[2],1,1,n))
