马上就又要考试了，复习一下板子，以前学线段树的时候还很懵，现在回过头来补一下档。。。
如题，已知一个数列，你需要进行下面两种操作：
1.将某区间每一个数加上x
2.求出某区间每一个数的和
第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3或4个整数，表示一个操作，具体如下：
操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k
操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和
输出格式：输出包含若干行整数，即为所有操作2的结果。
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
11
8
20
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=8，M<=10
对于70%的数据：N<=1000，M<=10000
对于100%的数据：N<=100000，M<=100000
（数据已经过加强^_^，保证在int64/long long数据范围内）
样例说明：
Solution：
本题是最基础的线段树模板——区间加减、区间求和。
简单讲一下线段树（鉴于线段树网上的讲解已经十分清楚详细，我就随便将点理解）：
线段树是一种基于分治思想的二叉树结构，用于区间上进行信息统计。
线段树的每个节点维护的是一个区间; 线段树具有唯一的根节点表示整个统计范围（$[1,n]$）; 线段树的每个叶子节点都表示一个长度为1的单元区间（$[x,x]$）; 对于每个内部节点$[l,r]$，它的左子节点为$[l,mid]$，右子节点为$[mid+1,r]$，其中$mid=(l+r)/2$。
建树：
根节点编号为$1$，编号为x的左子节点为$x*2$，右儿子节点为$x*2+1$。依此，递归建树，同时在递归过程中预处理所需信息（以本题为例，在递归建树时我们可以维护出每个子区间的和）。容易发现，当有N个叶子节点时，该树总共的节点数最多为$N+N/2+N/4+…+2+1=2N-1$（即一颗满二叉树）。于是保存线段树的数组长度至少为$4N$，才能保证不会越界。
区间修改：
从上往下递归，判断区间是否包含，若当前的区间完全被$[l,r]$覆盖则直接更改，若不覆盖则继续递归左右儿子节点，这里我的代码实现时用到了延迟标记（add[rt]表示编号rt的区间所增加的值），顾名思义就是先不将修改的值下放到子区间中而是在当前区间要被修改或被查询时再进行修改（详见代码）。最后记得回溯时维护所需信息（本题中的区间和）。
区间查询：
与区间修改类似，判断区间是否包含，若被完全覆盖直接回溯并返回当前区间的信息（本题中的区间和），否则就继续递归左右儿子节点，当然也得记得要在找到完全覆盖区间之前下放延迟标记。最后返回所需的区间信息就ok了(本题中的区间和)。
讲的不够清楚，不理解可以看代码或自行百度～～手动滑稽～～
代码：
1 // luogu-judger-enable-o2 2 #include<bits/stdc++.h> 3 #define il inline 4 #define ll long long 5 #define debug printf("%d %s\n",__LINE__,__FUNCTION__) 6 #define lson l,m,rt<<1 7 #define rson m+1,r,rt<<1|1 8 using namespace std; 9 const int N=100005; 10 ll n,m,sum[N<<2],add[N<<2]; 11 il ll gi() 12 { 13 ll a=0;char x=getchar();bool f=0; 14 while((x<‘0‘||x>‘9‘)&&x!=‘-‘)x=getchar(); 15 if(x==‘-‘)x=getchar(),f=1; 16 while(x>=‘0‘&&x<=‘9‘)a=a*10+x-48,x=getchar(); 17 return f?-a:a; 18 } 19 il void pushup(int rt){sum[rt]=sum[rt<<1]+sum[rt<<1|1];} 20 il void pushdown(int rt,int m) 21 { 22 if(add[rt]){ 23 add[rt<<1]+=add[rt]; 24 add[rt<<1|1]+=add[rt]; 25 sum[rt<<1]+=add[rt]*(m-(m>>1)); 26 sum[rt<<1|1]+=add[rt]*(m>>1); 27 add[rt]=0; 28 } 29 } 30 il void build(int l,int r,int rt) 31 { 32 add[rt]=0; 33 if(l==r){sum[rt]=gi();return;} 34 int m=l+r>>1; 35 build(lson),build(rson); 36 pushup(rt); 37 } 38 il void update(int L,int R,ll c,int l,int r,int rt) 39 { 40 if(L<=l&&R>=r){ 41 add[rt]+=c; 42 sum[rt]+=(ll)c*(r-l+1); 43 return ; 44 } 45 pushdown(rt,r-l+1); 46 int m=l+r>>1; 47 if(L<=m)update(L,R,c,lson); 48 if(m<R)update(L,R,c,rson); 49 pushup(rt); 50 } 51 il ll query(int L,int R,int l,int r,int rt) 52 { 53 if(L<=l&&R>=r)return sum[rt]; 54 pushdown(rt,r-l+1); 55 int m=l+r>>1; 56 ll ret=0; 57 if(L<=m)ret+=query(L,R,lson); 58 if(m<R)ret+=query(L,R,rson); 59 return ret; 60 } 61 int main() 62 { 63 n=gi(),m=gi(); 64 build(1,n,1); 65 ll u,x,y,k; 66 while(m--){ 67 u=gi(); 68 if(u==1){ 69 x=gi(),y=gi(),k=gi(); 70 update(x,y,k,1,n,1); 71 } 72 else { 73 x=gi(),y=gi(); 74 printf("%lld\n",query(x,y,1,n,1)); 75 } 76 } 77 return 0; 78 }
原文：https://www.cnblogs.com/five20/p/8763190.html