假设有编号从1到n的n个点，每个点都存了一些信息，用[L,R]表示下标从L到R的这些点。
线段树的用处就是，对编号连续的一些点进行修改或者统计操作，修改和统计的复杂度都是O(log2(n)).
线段树的原理，就是，将[1,n]分解成若干特定的子区间(数量不超过4*n),然后，将每个区间[L,R]都分解为
少量特定的子区间，通过对这些少量子区间的修改或者统计，来实现快速对[L,R]的修改或者统计。
一.基本概念及其形状
1.使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，实际应用时一般还要开4N的数组以免越界，因此有时需要离散化让空间压缩。
3.线段树的基本思想：二分
4.线段树的一般结构：
由上图可以看出每个叶子节点的区间都是[L,mid],[mid+1,R]，L代表上一个区间的左端点，R代表上一个区间的右端点，mid代表上面左右区间的中间值。所以线段树是很有规律的。
二.解决题目的基本操作
1.首先一般求解树的问题，都是先要建树。线段树也不例外，建树一般都是模板的。如下：
const int maxn=10000; //一般为点的总个数
int a[maxn+5],st[maxn+5];
int sum[maxn*4+1];
void pushup(int rt){
sum[rt]=sum[rt*2]+sum[rt*2+1]; //这里是求和的pushup，如果求max就改成sum[rt]=max(sum[rt*2],sum[rt*2+1]这个样子。
} //用来把当前节点信息更新到父节点 (求和更新)
void build(int l,int r,int rt){ //rt表示当前子树的根，也就是当前所在的节点
if(l==r){ //如果左端点等于右端点,则说明到了底端叶子节点则返回
st[rt]=a[l];
return ;
}
int m=(l+r)/2;
build(l,m,rt*2); //构建左子树
build(m+1,r,rt*2+1); //构建右子树
pushup(rt);
}
2.建好树了后对于题目就会有一系列的要求，比如单点替换（更新），求区间最值，求区间和之类的
点修改：
void update(int l,int r,int p,int add,int rt){ // add为要增加的数，p代表判断要更新的数字，
if(l==r){
sum[rt]+=add; //如果是叶节点则修改
return ;
}
int m=(l+r)/2;
if(p<=m) update(l,m,p,add,rt*2); //左边l，右边m
else update(m+1,r,p,add,rt*2+1); //左边m+1，右边 r
pushup(rt);
}
区间求和：
int query(int L,int R,int l,int r int rt){ //[L,R]表示操作区间，[l,r]表示总区间，rt表示当前节点编号
if(L<=l && R>=r){ //在区间内直接返回
return sum[rt];
}
int m=(l+r)/2; //左子区间：[L,m] 右子区间：[m+1,R] 求和区间：[l,r]
int ans;
if(L<=m) ans+=query(L,R,l,m,rt*2); //左子区间与[l,r]有重叠，递归
if(R>m) ans+=query(L,R,m+1,r,rt*2+1); //右子区间与[l,r]有重叠，递归
return ans;
}
区间求最大值:
int query(int L,int R,int l,int r,int rt){//L,R查询的区间,l,r总区间
if(L<=l&&R>=r){
return Max[rt];
}
int ans=0;
int m=(l+r)/2;
if(L<=m) ans=max(ans,query(L,R,l,m,ls));
if(R>m) ans=max(ans,query(L,R,m+1,r,rs));
return ans;
}
三.区间方面的线段树
在做区间修改的时候，有个叫懒惰标记（延迟标记）。
所以, 每次进行值的更新和查询操作, 每到一个有 lazy 标记的结点, 必须进行向下更新.
即，如果要给一个区间的所有值都加上1，那么，实际上并没有给这个区间的所有值都加上1，而是打个标记，记下来，这个节点所包含的区间需要加1.打上标记后，要根据标记更新本节点的统计信息，比如，如果本节点维护的是区间和，而本节点包含5个数，那么，打上+1的标记之后，要给本节点维护的和+5。这是向下延迟修改，但是向上显示的信息是修改以后的信息，所以查询的时候可以得到正确的结果。有的标记之间会相互影响，所以比较简单的做法是，每递归到一个区间，首先下推标记（若本节点有标记，就下推标记），然后再打上新的标记，这样仍然每个区间操作的复杂度是O(log2(n))。
标记有相对标记和绝对标记之分：
相对标记是将区间的所有数+a之类的操作，标记之间可以共存，跟打标记的顺序无关（跟顺序无关才是重点）。
所以，可以在区间修改的时候不下推标记，留到查询的时候再下推。
注意：如果区间修改时不下推标记，那么PushUp函数中，必须考虑本节点的标记。
而如果所有操作都下推标记，那么PushUp函数可以不考虑本节点的标记，因为本节点的标记一定已经被下推了（也就是对本节点无效了）
绝对标记是将区间的所有数变成a之类的操作，打标记的顺序直接影响结果，
所以这种标记在区间修改的时候必须下推旧标记，不然会出错。
注意，有多个标记的时候，标记下推的顺序也很重要，错误的下推顺序可能会导致错误。
之所以要区分两种标记，是因为非递归线段树只能维护相对标记。
因为非递归线段树是自底向上直接修改分成的每个子区间，所以根本做不到在区间修改的时候下推标记。
非递归线段树一般不下推标记，而是自下而上求答案的过程中，根据标记更新答案。
所以来说，做普通的线段树单点更新和区间查询的时候用不到这个懒惰标记，而做区间更新修改的时候就要加点东西了，而且上面的有些函数也需要加一点东西了。
而且看大佬们一般都用位运算好想说位运算比普通的乘除快，所以基本的先熟悉一下，rt<<1代表位左移一位，就是乘2，rt>>1代表位右移一位，就是除2, rt | 1 就代表加1。
区间更新与点更新不同，它需要更深层次的理解，最为基本的Add(L, R, V)与Query(L,R)系列，然后以此为基础可以衍射出其他各种做法：例如Set(L, R, V)系列就是其衍射品，Set系列更改的就是在查询的时候读取到Lazy标记就立刻返回，而Add系列不同，他要一直往下读它的Lazy标记。
首先是pushdown的模板：
void push_down(ll m,ll rt){ //m为总区间长度
if(lazy[rt]){
lazy[ls]+=lazy[rt];
lazy[rs]+=lazy[rt];
sum[ls]+=lazy[rt]*(m-(m>>1));
sum[rs]+=lazy[rt]*(m>>1);
lazy[rt]=0;
}
}
最后是区间更新，更新从根向下，若是（L,R）包含了这个根所在的区间，就直接给这个区间附上lazy标记并且返回，否则就说明有冗余的东西，就得把目前这个点的lazy也下推，然后在新的区间继续找新的值。
void update(ll L,ll R,ll c,ll l,ll r,ll rt){//区间更新[l,r],[L,R]代表总区间
if(l<=L&&r>=R){
lazy[rt]+=c;
sum[rt]+=c*(R-L+1);
return ;
}
push_down(R-L+1,rt); //所有的节点都更新一遍lazy标记
ll m=(L+R)>>1; //总区间的一半
if(l<=m) update(L,m,c,l,r,ls); //注意这里递归的是总区间为变量
if(r>m) update(m+1,R,c,l,r,rs);
push_up(rt);
}
经常自己翻自己博客发现还是得给自己加个板子来结合。
所以贴一个板子题：
#include<stdio.h>
const int maxn=50000;
int sum[maxn*4+1];
void pushup(int rt){
sum[rt]=sum[rt*2]+sum[rt*2+1];
}
void build(int l,int r,int rt){
if(l==r){
scanf("%d",&sum[rt]);
return ;
}
int m=(l+r)/2;
build(l,m,rt*2);
build(m+1,r,rt*2+1);
pushup(rt);
}
void update(int l,int r,int p,int add,int rt){
if(l==r){
sum[rt]+=add;
return ;
}
int m=(r+l)/2;
if(p<=m) update(l,m,p,add,rt*2);
else update(m+1,r,p,add,rt*2+1);
pushup(rt);
}
int query(int L,int R,int l,int r,int rt){
if(l<=L&&r>=R) return sum[rt];
int ans=0;
int m=(L+R)/2;
if(l<=m) ans+=query(L,m,l,r,rt*2);
if(r>m) ans+=query(m+1,R,l,r,rt*2+1);
return ans;
}
int main()
{
int t;
char d[10];
scanf("%d",&t);
for(int a=1;a<=t;a++){
printf("Case %d:
", a);
int n;
scanf("%d",&n);
build(1,n,1);
while(scanf("%s",d)!=EOF){
if(d[0]=='E') break;
int x,y; //x营地,y人 或 x，y区间
scanf("%d%d",&x,&y);
if(d[0]=='Q') {
int h=query(1,n,x,y,1);
printf("%d
",h);
}
if(d[0]=='U') update(1,n,x,y,1);
if(d[0]=='S') update(1,n,x,-y,1);
}
}
return 0;
}