是一种二叉搜索树，通过二分法访问或修改区间值，区间大小不超过10^6，区间值必须满足区间加法，即仅当对于区间 [ L , R ] 的问题的答案可以由 [ L , M ] 和 [ M + 1 , R ]的答案合并得到。
时间复杂度为log级
需要的数据：
arr[maxn],记录区间中的单点值
tree[maxn<<2]线段树数组
lazy[maxn<<2]延迟更新数组
操作流程
0.初始化
定义void型pushup函数，传入参数k,用k的儿子节点k<<1,k<<1|1,区间加法更新k节点
定义void型pushdown函数，传入参数k,更新k节点的儿子节点k<<1,k<<1|1，更新后lazy[k<<1]+=lazy[k]，lazy[k<<1|1]+=lazy[k]，lazy[k]=0表示k更新完毕，并将更新值传入儿子的延迟更新值
定义void型build递归函数构建线段树，传入参数（l=1,r=n,k=1）,(l，r)表示当前递归层访问到的区间,初始值始终为（1，n）,k表示当前区间（l,r）对应在线段树tree中的下标，初始值始终为1
build函数利用二分法搜索区间{（1，1），（2，2），（3，3）……}（l==r即为单点）对应在线段树tree的下标k,并赋值tree[k]为arr[l]，表示区间（l,l）的值等于单点arr[l]的值
回溯时需要调用pushup函数，用儿子节点更新当前递归层的k节点
1.区间更新
定义void型change递归函数进行区间更新，传入参数（l=1,r=n,k=1,cl,cr,x）,(l，r)表示当前递归层访问到的区间,初始值始终为（1，n）,k表示当前区间（l,r）对应在线段树tree中的下标，初始值始终为1，(cl,cr)表示更新的区间,x表示更新的值
当（l，r）被包含在（cl,cr）中时，lazy[k]+=x表示将用x延迟更新区间（l,r)的父亲节点的值,并用x对当前区间（l,r）更新
调用pushdown函数，用当前递归层的k节点更新自己的儿子节点
设mid为（l+r）>>1,如果cl<=mid,递归至（l,mid,k<<1,cl,cr,x）,查询（l,mid）区间，如果cr>mid，递归至（mid+1,r,k<<1|1,cl,cr,x）,查询（mid+1,r）区间
回溯时需要调用pushup函数，用儿子节点更新当前递归层的k节点
2.区间查询
定义int 型query递归函数，传入参数（l=1,r=n,k=1,ql,qr）,(l，r)表示当前递归层访问到的区间,初始值始终为（1，n）,k表示当前区间（l,r）对应在线段树tree中的下标，初始值始终为1，(ql,qr)表示查询的区间
当（l，r）被包含在（cl,cr）中时，返回tree[k]，即该区间的值
调用pushdown函数，用当前递归层的k节点更新自己的儿子节点
设a为当前区间（l,r）的区间值
设mid为（l+r）>>1,如果cl<=mid,递归至（l,mid,k<<1,cl,cr,x）,（l,mid）区间，如果cr>mid，递归至（mid+1,r,k<<1|1,cl,cr,x）,查询（mid+1,r）区间
更新a值为 区间加法(（l,mid）值，（mid+1,r）值)，返回a
难点
步骤繁杂，容易出错，debug困难
优化
1.动态开点，可节约空间，tree和lazy的大小减小到maxn<<1,用lson[maxn<<1],rson[maxn<<1]记录每个节点的左右孩子的下标,在build和change时需要在函数体最开头加if(!k)k=++cnt，在query时需要在函数体最开头加if(!k)return 0.
2.离散化，可压缩区间，极大节约空间，但会浪费时间，目前尚未实现
伪代码：
int tree[maxn<<2],lazy[maxn<<2]; void pushdown(int m,int k) { if(lazy[k]) { lazy[k<<1]+=lazy[k]; lazy[k<<1|1]+=lazy[k]; tree[k<<1]+= (m - (m>>1))*lazy[k]; tree[k<<1|1]+=(m>>1)*lazy[k]; lazy[k]=0; } } void build(int l,int r,int k) { if(l==r) { scanf("%lld",&tree[k]); return; } int mid=(l+r)>>1; build(l,mid,k<<1); build(mid+1,r,k<<1|1); tree[k]=tree[k<<1]+tree[k<<1|1]; } int query(int l,int r,int k,int ql,int qr) { if(ql <= l&&r <= qr)return tree[k]; int sum=0; int mid=(l+r)>>1; pushdown(r-l+1,k); if(ql<=mid)sum+= query(l,mid,k<<1,ql,qr); if(qr>mid)sum+= query(mid+1,r,k<<1|1,ql,qr); return sum; } void change(int l,int r,int k,int cl,int cr,int x) { if(cl <= l&&r <= cr) { tree[k]+=(ll)(r-l+1)*x; lazy[k]+=x; return; } pushdown(r-l+1,k); int mid=(l+r)>>1; if(cl<=mid)change(l,mid,k<<1,cl,cr,x); if(cr>mid)change(mid+1,r,k<<1|1,cl,cr,x); tree[k]=tree[k<<1]+tree[k<<1|1]; }
原文地址：http://www.cnblogs.com/alineyyds/p/16851103.html
