转自 http://www.cnblogs.com/aiguona/p/7337938.html
线段树
一、基本概念
1、线段树是一棵二叉搜索树，它储存的是一个区间的信息。
2、每个节点以结构体的方式存储，结构体包含以下几个信息：
区间左端点、右端点；（这两者必有）
这个区间要维护的信息（事实际情况而定，数目不等）。
3、线段树的基本思想：二分。
4、线段树一般结构如图所示：
5、特殊性质：
由上图可得，
1、每个节点的左孩子区间范围为[l，mid]，右孩子为[mid+1,r]
2、对于结点k，左孩子结点为2*k，右孩子为2*k+1，这符合完全二叉树的性质
二、线段树的基础操作
注：以下基础操作均以引例中的求和为例，结构体以此为例：
struct node
{
int left,right;//左右
int weight;//权值
int flag;//延迟标记
} tree[400001];线段树的基础操作主要有5个：
建树、单点查询、单点修改、区间查询、区间修改。
1、建树，即建立一棵线段树
① 主体思路：
a、对于二分到的每一个结点，给它的左右端点确定范围。
b、如果是叶子节点，存储要维护的信息。
c、状态合并。
②代码
void build(int k,int ll,int rr)//建树，k是父亲节点，ll、rr左右孩子
{
tree[k].left=ll,tree[k].right=rr;
if(tree[k].left==tree[k].right)//如果是叶子结点，直接赋值
{
scanf("%d",&tree[k].weight);
return;
}
int m=(ll+rr)/2;
build(k*2,ll,m);
build(k*2+1,m+1,rr);
tree[k].weight=tree[k*2].weight+tree[k*2+1].weight;//求区间和，所以父亲结点是左右孩子的和
}③注意
a.结构体要开4倍空间，因为叶子节点的存储并不是按顺序存储的。
b.千万不要漏了return语句，因为到了叶子节点不需要再继续递归了。
2、单点查询，即查询一个点的状态，设待查询点为x
①主体思路：与二分查询法基本一致，如果当前枚举的点左右端点相等，即叶子节点，就是目标节点。如果不是，因为这是二分法,所以设查询位置为x，当前结点区间范围为了l，r，中点为mid，则如果x<=mid，则递归它的左孩子，否则递归它的右孩子
②代码
void ask_point(int k)//单点查询
{
if(tree[k].left==tree[k].right)
{
ans=tree[k].weight;
return ;
}
if(tree[k].flag) down(k);
int m=(tree[k].left+tree[k].right)/2;
if(x<=m) ask_point(k*2);
else ask_point(k*2+1);
}3、单点修改，即更改某一个点的状态。用引例中的例子，对第x个数加上y
①主体思路
结合单点查询的原理，找到x的位置；根据建树状态合并的原理，修改每个结点的状态。
②代码
void change_point(int k)//单点修改，第x个数加上y
{
if(tree[k].left==tree[k].right)
{
tree[k].weight+=y;
return;
}
if(tree[k].flag) down(k);
int m=(tree[k].left+tree[k].right)/2;
if(x<=m) change_point(k*2);
else change_point(k*2+1);
tree[k].weight=tree[k*2].weight+tree[k*2+1].weight;
}4、区间查询，即查询一段区间的状态，在引例中为查询区间[x,y]的和
①主体思路
②代码
void ask_interval(int k)//区间查询，查询区间和
{
if(tree[k].left>=a&&tree[k].right<=b)
{
ans+=tree[k].weight;
return;
}
if(tree[k].flag) down(k);
int m=(tree[k].left+tree[k].right)/2;
if(a<=m) ask_interval(k*2);
if(b>m) ask_interval(k*2+1);
}5、区间修改，即修改一段连续区间的值，我们已给区间[a,b]的每个数都加x为例讲解
Ⅰ.引子
有人可能就想到了：
修改的时候只修改对查询有用的点。
对，这就是区间修改的关键思路。
为了实现这个，我们引入一个新的状态——延迟标记。
Ⅱ 延迟标记
1、直观理解：“延迟”标记，用到它才动，不用它就不动。
2、作用：存储到这个节点的修改信息，暂时不把修改信息传到子节点。
3、实现思路（重点）：
a.原结构体中增加新的变量，存储这个延迟标记。
b.递归到这个节点时，只更新这个节点的状态，并把当前的更改值累积到标记中。
c.当需要递归这个节点的子节点时，标记下传给子节点。这里不必管用哪个子节点，两个都传下去。
d.下传操作：
3部分：①当前节点的延迟标记累积到子节点的延迟标记中。
②修改子节点状态。在引例中，就是原状态+子节点区间点的个数*父节点传下来的延迟标记。
③父节点延迟标记清0。
延迟标记下穿代码：flag为懒标记，其余变量与前面含义一致。
延迟标记代码：
void down(int k)//延迟标记下传
{
tree[k*2].flag+=tree[k].flag;
tree[k*2+1].flag+=tree[k].flag;
tree[k*2].weight+=tree[k].flag*(tree[k*2].right-tree[k*2].left+1);
tree[k*2+1].weight+=tree[k].flag*(tree[k*2+1].right-tree[k*2+1].left+1);
tree[k].flag=0;
}区间修改代码
void change_interval(int k)//区间修改，把a-b之间数改成k
{
if(tree[k].left>=a&&tree[k].right<=b)
{
tree[k].weight+=(tree[k].right-tree[k].left+1)*y;
tree[k].flag+=y;
return;
}
if(tree[k].flag) down(k);
int m=(tree[k].left+tree[k].right)/2;
if(a<=m) change_interval(k*2);
if(b>m) change_interval(k*2+1);
tree[k].weight=tree[k*2].weight+tree[k*2+1].weight;
}三、线段树五种操作模板
//#include <bits/stdc++.h>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define IO ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
typedef long long LL;
const long long INF = 0x3f3f3f3f;
const long long mod = 1e9+7;
const double PI = acos(-1.0);
const int maxn = 100000;
const char week[7][10]= {"Monday","Tuesday","Wednesday","Thursday","Friday","Saturday","Sunday"};
const char month[12][10]= {"Janurary","February","March","April","May","June","July",
"August","September","October","November","December"
};
const int daym[2][13] = {{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
{0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}
};
const int dir4[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const int dir8[8][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}};
using namespace std;
LL n,m;//n个结点，m种操作，操作为p
LL ans;//存储答案
struct node
{
LL left,right;//左右
LL weight;//权值
LL flag;//延迟标记
} tree[410000];
void build(LL k,LL ll,LL rr)//建树，k是父亲节点，ll、rr左右孩子
{
tree[k].left=ll,tree[k].right=rr;
if(tree[k].left==tree[k].right)//如果是叶子结点，直接赋值
{
scanf("%lld",&tree[k].weight);
return;
}
LL m=(ll+rr)/2;
build(k*2,ll,m);
build(k*2+1,m+1,rr);
tree[k].weight=tree[k*2].weight+tree[k*2+1].weight;//求区间和，所以父亲结点是左右孩子的和
}
void down(LL k)//延迟标记下传
{
tree[k*2].flag+=tree[k].flag;
tree[k*2+1].flag+=tree[k].flag;
tree[k*2].weight+=tree[k].flag*(tree[k*2].right-tree[k*2].left+1);
tree[k*2+1].weight+=tree[k].flag*(tree[k*2+1].right-tree[k*2+1].left+1);
tree[k].flag=0;
}
void ask_point(LL k,LL x)//单点查询
{
if(tree[k].left==tree[k].right)
{
ans=tree[k].weight;
return ;
}
if(tree[k].flag) down(k);
LL m=(tree[k].left+tree[k].right)/2;
if(x<=m) ask_point(k*2,x);
else ask_point(k*2+1,x);
}
void change_point(LL k,LL x,LL y)//单点修改，第x个数加上y
{
if(tree[k].left==tree[k].right)
{
tree[k].weight+=y;
return;
}
if(tree[k].flag) down(k);
LL m=(tree[k].left+tree[k].right)/2;
if(x<=m) change_point(k*2,x,y);
else change_point(k*2+1,x,y);
tree[k].weight=tree[k*2].weight+tree[k*2+1].weight;
}
void ask_interval(LL k,LL a,LL b)//区间查询，查询区间和
{
if(tree[k].left>=a&&tree[k].right<=b)
{
ans+=tree[k].weight;
return;
}
if(tree[k].flag) down(k);
LL m=(tree[k].left+tree[k].right)/2;
if(a<=m) ask_interval(k*2,a,b);
if(b>m) ask_interval(k*2+1,a,b);
}
void change_interval(LL k,LL a,LL b,LL y)//区间修改，把a-b之间数改成k
{
if(tree[k].left>=a&&tree[k].right<=b)
{
tree[k].weight+=(tree[k].right-tree[k].left+1)*y;
tree[k].flag+=y;
return;
}
if(tree[k].flag) down(k);
LL m=(tree[k].left+tree[k].right)/2;
if(a<=m) change_interval(k*2,a,b,y);
if(b>m) change_interval(k*2+1,a,b,y);
tree[k].weight=tree[k*2].weight+tree[k*2+1].weight;
}
int main()
{
scanf("%d",&n);//n个节点
scanf("%d",&m);//m种操作
build(1,1,n);//建树，传值根节点1，左孩子1，有孩子n
for(int i=1; i<=m; i++)
{
int p;
getchar();
scanf("%d",&p);
ans=0;
/*以下操作传值过去的为根节点1*/
if(p==1)
{
LL x;
scanf("%lld",&x);
ask_point(1,x);//单点查询,输出第x个数
printf("%lld",ans);
}
else if(p==2)
{
LL x,y;
scanf("%lld%lld",&x,&y);
change_point(1,x,y);//单点修改
}
else if(p==3)
{
LL a,b;
scanf("%lld%lld",&a,&b);//区间查询
ask_interval(1,a,b);
printf("%lld
",ans);
}
else if(p==4)//每段都加上一个数
{
LL a,b,y;
scanf("%lld%lld%lld",&a,&b,&y);//区间修改
change_interval(1,a,b,y);
}
}
}