1、线段树是一棵二叉搜索树，它储存的是一个区间的信息。

2、每个节点以结构体的方式存储，结构体包含以下几个信息：

区间左端点、右端点；（这两者必有）

这个区间要维护的信息（按实际情况而定，数目不等）。

3、线段树的基本思想：二分。

空间大小：

首先是开辟空间，一般设置节点数为N的4倍。证明如下：二叉树是等比数列求和。

公式中a1为首项，an为数列第n项，q为等比数列公比，Sn为前n项和。

x为树的层数，为树的高度+1。二叉树的高度为log2(n)<log2(n)+1，化简可得

整理之后即为4n。

解决问题：

例1：给出n个数，n<=1000000，和m个操作，每个操作可能有两种：1在某个位置加上一个数；2询问区间[l，r]的和，并输出。

例2：给出n个数，n<=1000000，和m个操作，每个操作修改一段连续区间[a,b]的值。

struct node{	int l; //left	int r; //right	int v; //value，这里是求和 int lazy; //懒惰标记}t[maxn*4]; //tree

普通版本的线段树进行的是 单点更新 和　区间查询 。对于带有 懒惰标记 的线段树, 则可以进行 区间更新。懒惰标记记录当前更新值。

void PushUp(int k)//由左孩子、右孩子向上更新父节点{ t[k].v = t[k<<1].v + t[k<<1|1].v;}void build(int k,int l,int r) //建树， k当前节点下标，线段左为l，线段右为r{ t[k].lazy=0; t[k].l=l;t[k].r=r; //线段左端，线段右端 if(l==r) //线段长度为零，结束 { scanf("%d",&t[k].v); return ;  }  int mid=(l+r)>>1; //取线段中点 build(k<<1,l,mid); //k<<1:下标为k节点的左儿子下标，线段左为l，线段右为mid  build(k<<1|1,mid+1,r); //k<<1|1:下标为k节点的右儿子下标，线段左为mid+1，线段右为r PushUp(k); //状态合并，此结点的value为两个孩子的v之和}

向下更新

void PushDown(int k,int num) //向下更新 ,num为子树数量{ if (t[k].lazy) //懒惰标记 { t[k<<1].lazy= t[k<<1|1].lazy = t[k].lazy; t[k<<1].v += (num - (num >> 1)) * t[k].lazy; t[k<<1|1].v += ((num >> 1)) * t[k].lazy; t[k].lazy = 0; }}

更新区间

void Update(int L,int R,int c,int l,int r,int k){ //L,R表示操作区间，l,r表示当前节点区间，rt表示当前节点编号  if(L <= l && r <= R){ //如果本区间完全在操作区间[L,R]以内  t[k].v +=c*(r-l+1);//更新数字和，向上保持正确  t[k].lazy +=c;//增加标记，表示本区间的v正确，子区间的v仍需要根据lazy标记的值来调整  return ;  }  int m=(l+r)>>1;  PushDown(k,r-l+1); //这里判断左右子树跟[L,R]有无交集，有交集才递归  if(L <= m) Update(L,R,c,l,m,rt<<1);  if(R > m) Update(L,R,c,m+1,r,rt<<1|1);  PushUp(k);//更新本节点信息 } 

区间查询

int Query(int L,int R,int l,int r,int k){//L,R表示操作区间，l,r表示当前节点区间，k表示当前节点编号  if(L <= l && r <= R){  //在区间内，直接返回  return t[k].v;  }  int m=(l+r)>>1;  //下推标记，否则value可能不正确  PushDown(k,r-l+1);  //累计答案  int ANS=0;  if(L <= m) ANS+=Query(L,R,l,m,k<<1);  if(R > m) ANS+=Query(L,R,m+1,r,k<<1|1);  return ANS; }