假设有编号从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;}
三.区间方面的线段树
在做区间修改的时候，有个叫懒惰标记（延迟标记）。
即，如果要给一个区间的所有值都加上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 pushdown(int rt,int l,int r){ //向下传递lazy标记 if(lazy[rt]){ //懒惰标记存在 ll le=(r+l>>1)-l+1; //左子树的长度 ll re=r-l+1-le; //右子树的长度 lazy[rt<<1]+=lazy[rt]; lazy[rt<<1|1]+=lazy[rt]; sum[rt<<1]+=lazy[rt]*le; sum[rt<<1|1]+=lazy[rt]*re; lazy[rt]=0; //标记清零 } } 然后是查找，如果从根节点开始往下查找符合区间的点，那么久排除（L,R）区间之外的点，但如果此时的根节点范围过大，又有lazy标记，那么就同时要把lazy标记往下移动。
ll query(int L,int R,int l,int r,int rt){ if(L<=l&&R>=r){ return sum[rt]; } pushdown(rt,l,r); int m=(l+r)>>1; ll ret=0;j if(L<=m) ret+=query(L,R,lson); if(m 最后是区间更新，更新从根向下，若是（L,R）包含了这个根所在的区间，就直接给这个区间附上lazy标记并且返回，否则就说明有冗余的东西，就得把目前这个点的lazy也下推，然后在新的区间继续找新的值。
void update(int L,int R,int c,int l,int r,int rt){
if(L<=l&&r<=R){ lazy[rt]+=c; //要对sum求和，不然更新父节点值会少 sum[rt]=c*(r-l+1); return ; } int m=(l+r)>>1; pushdown(rt,l,r); //说明这个根节点的范围不在（L,R）范围内，要递归到下面去继续找 if(L<=m) update(L,R,c,lson); if(R>m) update(L,R,c,rson); sum[rt]=sum[rt<<1]+sum[rt<<1|1];}
最后是大佬的永久化标记代码，反正还不怎么懂。
//标记永久化（永久化标记）void push(int rt,int l,int r) //就是pushudown的作用{ if(lazy[rt]==0)return; ll le = (r+l>>1)-l+1; ll re = r-l+1-le; lazy[rt<<1] += lazy[rt]; lazy[rt<<1|1] += lazy[rt]; sum[rt<<1] += lazy[rt]*le; sum[rt<<1|1] += lazy[rt]*re; lazy[rt] = 0;}ll query(int l,int r,int rt,int ql,int qr){ if(ql<=l&&qr>=r) return sum[rt]; else { //push(rt,l,r); int mid = l + r>>1; ll ret = 1ll*(min(qr,r)-max(ql,l)+1) * lazy[rt]; if(ql<=mid) ret += query(l,mid,rt<<1,ql,qr); if(qr>mid) ret += query(mid+1,r,rt<<1|1,ql,qr); return ret; }}void update(int l,int r,int rt,int ql,int qr,int v){ if(ql<=l&&qr>=r) sum[rt] += 1LL*(r-l+1)*v,lazy[rt] += v; else { int mid = l+r>>1; if(ql<=mid) update(l,mid,rt<<1,ql,qr,v); if(qr>mid) update(mid+1,r,rt<<1|1,ql,qr,v); sum[rt] = sum[rt<<1] + sum[rt<<1|1] + lazy[rt]*(r-l+1); }
（以上内容基本上为各种博客所看到大佬们的知识，我只是按照自己学习顺序各种找一下..）