hihocoder上的这一篇文章写得特别赞。非常好理解。
转载于：http://hihocoder.com/contest/hiho19/problem/1
“在我介绍别的算法之前。你先来讲一讲你是准备怎样使用线段树来解决问题的吧？”小Hi尽管做好了解说的准备，可是还是希望可以一步步引导小Ho进行思考。于是这般说道。
“唔……那我先从线段树的定义说起吧：线段树事实上本质就是用一棵树来维护一段区间上和某个子区间相关的值——比如区间和、区间最大最小值一类的。
”小Ho说道：“它的详细做法是这种，这棵树的根节点表示了整段区间，根节点的左儿子节点表示了这段区间的前半部分，根节点的右儿子节点表示了这段区间的后半部分——并以此类推，对于这棵树的每一个节点。假设这个节点所表示的区间的长度大于1，则令其左儿子节点表示这段区间的前半部分。令其右儿子表示这段区间的后半部分。以一段长度为10的区间为例。我所建立出的线段树应该是这样子的。”
“画的还凑合，可是这样一棵树有什么用呢？”小Hi明知故问道。
“就以RMQ问题为例吧——RMQ问题要求的是求解一段区间中的最小值，那么我最好还是效仿ST算法。先对一些可能会用到的区间求解这个最小值！而既然我要是用线段树来解决问题的，那么我最好还是就将每个节点相应的区间中的最小值都求解出来。”小Ho道。
“那我给你这样一组数据，你将这个预处理的结果给我计算一下？”小Hi又出难题。
“好啊！你这数据正好也仅仅有10个位置，那么我便直接用这棵树了。”仅仅见小Ho刷刷两笔便在之前绘下的二叉树上写下了每一个节点相应的区间中的最小值：“其实这样一步相当好计算，因为每一个非叶子节点所相应的区间都正好由它的两个儿子节点所相应的区间拼凑而成——那么仅仅须要像ST那样，这样一个节点所相应的区间中的最小值便是它的两个儿子节点所相应的区间中的最小值中更小的那一个。这样我仅仅须要O(N)的时间复杂度就能够计算出这棵树来。”
小Hi点了点头。继续问道：“我算是明确了。可是你这样一棵树统计出来的区间比ST算法统计出来的区间要少了非常多。你还可以使用非常快的算法进行查询么？更何况还有改动呢？”
小Ho笑了笑：“我先从简单的说起吧——改动，当某个位置的商品的重量发生改变的时候，相应的。就是这棵树的某个叶子节点的值发生了变化——可是和ST算法不同，包括这个节点的区间。便仅仅有这个节点的全部祖先节点，而这种节点数量其实是非常少的——仅仅有O(log(N))级别。也就是说，当一次改动操作发生的时候。我仅仅须要改变数量在O(log(N))级别的节点的值就能够完毕操作了，改动的时间复杂度是O(log(N))。
”
小Hi道：“是这样没错~算你过关！可是呢，还是像我之前所说的，你是准备怎样使用数量在O(N)级别的区间来应付全部的询问呢？”
小Ho的笑容仍未退去：“这个事实上也非常easy。我要做的事情事实上就是——将一个询问的区间拆成若干个我已经计算出来的区间（在ST算法中是拆成了2个的区间）。这样对于这些区间已经计算出的最小值求最小值的话，我就能够知道询问的整个区间中的最小值是多少了！
”
“那你准备怎样分解询问的区间呢？”小Hi问道。
小Ho思索了一会。道：“这个问题事实上非常easy。我从线段树的根開始，对于当前訪问的线段树节点t, 设其相应的区间为[A, B], 假设询问的区间[l, r]全然处于前半段或者后半段——即r <= (A + B)/2或者l > (A + B) / 2，那么递归进入t相应的子节点进行处理（由于还有一棵子树中显然不会有不论什么区间须要用到）。否则的话，则把询问区间分成2部分[l, (A + B) / 2]和[(A + B) / 2 + 1, r]，而且分别进入t的左右子树处理这两段询问区间（由于2棵子树中显然都有区间须要用到）！
当然了，假设[A, B]正好覆盖了[l, r]的话，就能够直接返回之前计算的t这棵子树中的最小值了。还是之前那个样例。假设我要询问[3, 9]这段区间，我的终于结果会是这种——橙色部分标注的区间。”
“首先[3, 9]分解成了[3, 5]和[6, 9]两个区间，而[3, 5]分解成了[3, 3]和[4, 5]——均没有必要继续分解，[6, 9]分解成了[6, 8]和[9, 9]——相同也没有必要继续分解了。每一步的分解都是必要的，所以这已经是最好的分解方法了。”
小Hi惬意的点了点头，道：“听起来还不错？可是你这样分解的话。区间的个数你能保证么？万一非常多怎么办？”
小Ho思索了一会。接着道：“不会的。除了第一次分解成2个区间的操作可能会将区间个数翻倍外，之后每一次分解的时候所处理的区间都肯定有一条边是和当前节点相应的重合的（即l=A或者r=B），也就是说即使再进行分解，分解出的两个区间中也一定会有一个区间是不须要再进行分解的，也就是区间的总数是在深度这个级别的，所以也是O(logN)的。”
“看来你还挺清楚的，那么要不你再总结一下，我就算你过关。然后我们就能够開始解说后面的问题了~”
小Ho道：“好的！
首先我会依据初始数据，使用O(N)的时间构建一棵最原始的线段树，这个过程中我会使用子节点的值来计算父亲节点的值。从而避免冗余计算。然后对于每一次操作，假设是一次改动的话。我就将改动的节点和这个节点的全部祖先节点的值都进行更新，能够用O(logN)的时间复杂度完毕。而假设是一次询问的话。我会使用上面描写叙述的方法来对询问区间进行分解。这样尽管不像ST算法那样是O(1)。可是却实现了上一次所提到的‘平衡’，不管是改动还是查询的时间复杂度都是O(logN)的，所以我这个算法终于的时间复杂度会是O(N + Q * log(N))，在这个数据规模下是绰绰有余的！”
“嗯~ o(*￣▽￣*)o 不错哟~那么就到这里吧。”小Hi笑容满满道：“赶紧去吃早饭吧！”
对hdu 1166 经典题目敌兵布阵 （单点更新） 加了具体的解释
题意为给定n个数的序列，编号1到n，提供三种操作 add p x 把第p个数添加x。 sub p x 把第p个数减去x， query l r, 查询从l到r个数的和（即区间[l,r]的和）.
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
using namespace std;
const int maxn=50010;
struct SegTree
{
int l,r;
int sum;
}segTree[maxn<<2];
void Build(int i,int l,int r)
{
segTree[i].l=l;
segTree[i].r=r;
int mid=(l+r)>>1;
if(segTree[i].l==segTree[i].r)
{
scanf("%d",&segTree[i].sum);
return;//千万别忘了这一句!!!
}
Build(i<<1,l,mid);
Build((i<<1)|1,mid+1,r);
segTree[i].sum=segTree[i<<1].sum+segTree[(i<<1)|1].sum;
}
void Add(int i,int p,int add)
{
segTree[i].sum+=add;
int l=segTree[i].l;
int r=segTree[i].r;
if(l==r)
return;
int mid=(l+r)>>1;
//为什么这么写呢？改动某个点，仅仅要改动该点以及包括该点的祖先节点就好了；
//我们是从根节点開始相加的。那么最重要的任务就是推断根节点的左右孩子哪个包括所要改动的那个点，该点仅仅存在于一个孩子中，由于
//根节点的两个孩子所代表的区间是不相交的。所以我们要么去左孩子节点添加值。要么去右孩子节点添加值。怎么推断呢；对于根节点区间[L,R];
//令mid=(L+R)/2; 其左孩子代表的区间为[L,mid],右孩子区间代表的是[mid+1,R],这样就非常明显了。假设要改动的位置<=mid时。那我们肯定是要去左
//孩子的。由于仅仅有左孩子的区间才包括该点啊，相反假设>mid时，就仅仅能去右孩子了。这里就是关键。所以添加的操作就是从根节点開始向下。不断拐弯
//不断添加值，直到找到叶子节点为止。
if(p<=mid)
Add(i<<1,p,add);
else
Add((i<<1)|1,p,add);
}
int Sum(int i,int l,int r)
{
//为什么这么写呢？该功能是查询区间[l,r]的和。我们称其为目标区间；
//我们是从根节点開始查询的。
//首先考虑的是究竟是查询根节点本身，还是它的左孩子。还是它的右孩子呢，假设l,r正好是根节点所代表的区间，那么直接返回根节点的sum值就能够了
//假设不是的话。就要考虑到左右孩子去了。设根节点区间[L,R]。令mid=(L+R)/2,则左孩子区间为[L,mid],右孩子区间为[mid+1,R],如何依据孩子区间去找目标区间呢
//假设目标区间的r<=mid时。那么该目标区间一定存在左孩子中。假设目标区间的l>mid时，那么目标区间一定存在右孩子中。假设mid在l,r之间时。那么我们就要
//查询左右两个孩子。
//注意，假设所建的树中当查询到某一个节点时。其节点代表的区间正好是该函数的參数时，那么查到该节点就直接返回其sum值就可以，无需向下查询到叶子节点
// 假设没有的话。那么就得查询到叶子节点，把叶子节点的sum值相加
// if(segTree[i].l==segTree[i].r)//这一句写的大错特错!!!定要注意
// return segTree[i].sum;
if(segTree[i].l==l&&segTree[i].r==r)
return segTree[i].sum;
int ans=0;
int mid=((segTree[i].l+segTree[i].r)>>1);
if(r<=mid)
ans=Sum(i<<1,l,r);
else if(l>mid)
ans=Sum((i<<1)|1,l,r);
else
ans=Sum(i<<1,l,mid)+Sum((i<<1)|1,mid+1,r);
return ans;
}
int main()
{
char cm[10];
int n;
int t;scanf("%d",&t);
int p,add,l,r;
for(int cas=1;cas<=t;++cas)
{
printf("Case %d:
",cas);
scanf("%d",&n);
Build(1,1,n);
while(scanf("%s",cm))
{
if(cm[0]=='E')
break;
if(cm[0]=='A')
{
scanf("%d%d",&p,&add);
Add(1,p,add);
}
else if(cm[0]=='S')
{
scanf("%d%d",&p,&add);
Add(1,p,-add);
}
else
{
scanf("%d%d",&l,&r);
printf("%d
",Sum(1,l,r));
}
}
}
return 0;
}
个人理解：线段树是一种树形数据结构。是对给定的一段区间进行操作，树中的每一个节点都代表一段区间，每一个节点保存的是其代表区间的左边界。右边界。以及其它信息（比方代表区间的最小值。最大值或总和）。当中根节点代表的是总区间[1,n]，其节点的编号为1，对于每一个非叶子节点，假设节点编号为i。把其代表的区间[l,r]分成两部分分别保存在左右孩子中，定义mid=(l+r)/2 （mid=（l+r)>>1等价）,当中左孩子代表的区间为[l,mid],编号为i*2
(i<<1等价）,右孩子代表的区间为[mid+1,r]。编号为i*2+1 ((i<<1)|1)等价。叶子节点非常关键。保存原始的输入数据，其节点编号不确定。假设总的区间是[1,n]，那么一定有n个叶子节点，也就是每一个叶子节点代表总区间中的'1'。
操作：
1.建树。
是一个递归的过程。非叶子节点保存的其它信息值由其孩子节点确定。
2.单点更新。 比方对某个叶子节点添加或该边其值，那么树上的其他节点也要改变保存的信息值（比方最大值，最小值等等）,值得注意的是，非叶子节点不用所有更新，仅仅须要更新与叶子节点有关系的非叶子节点。
这也是一个递归的过程，从根节点開始递归。一直走到叶子节点，走得过程是一个“来回拐弯”的过程，有且仅仅有一条路径，递归到更新的叶子
节点。进行更新，然后“原路返回”更新路径上的非叶子节点的其它信息值。
以添加叶子节点的值为例。
改动某个点，仅仅要改动该点以及包括该点的祖先节点就好了；
我们是从根节点開始相加的。那么最重要的任务就是推断根节点的左右孩子哪个包括所要改动的那个点，该点仅仅存在于一个孩子中，由于
根节点的两个孩子所代表的区间是不相交的。所以我们要么去左孩子节点添加值。要么去右孩子节点添加值。怎么推断呢。对于根节点区间[L,R];
令mid=(L+R)/2; 其左孩子代表的区间为[L,mid],右孩子区间代表的是[mid+1,R],这样就非常明显了。假设要改动的位置<=mid时，那我们肯定是要去左
孩子的，由于仅仅有左孩子的区间才包含该点啊，相反假设>mid时，就仅仅能去右孩子了。这里就是关键，所以添加的操作就是从根节点開始向下，不断拐弯
。直到找到叶子节点为止，更新。然后原路返回。边返回边更新非叶子节点。
3.查询。
以添加叶子节点的值为例。
该功能是查询区间[l,r]的和。我们称其为目标区间。
我们是从根节点開始查询的。
首先考虑的是究竟是查询根节点本身。还是它的左孩子，还是它的右孩子呢。假设l,r正好是根节点所代表的区间，那么直接返回根节点的sum值就能够了
假设不是的话，就要考虑到左右孩子去了，设根节点区间[L,R]，令mid=(L+R)/2,则左孩子区间为[L,mid],右孩子区间为[mid+1,R],如何依据孩子区间去找目标区间呢
假设目标区间的r<=mid时，那么该目标区间一定存在左孩子中，假设目标区间的l>mid时，那么目标区间一定存在右孩子中，假设mid在l,r之间时。那么我们就要
查询左右两个孩子。
注意，假设所建的树中当查询到某一个节点时，其节点代表的区间正好是该函数的參数时，那么查到该节点就直接返回其sum值就可以，无需向下查询到叶子节点
假设没有的话，那么就得查询到叶子节点。把叶子节点的sum值相加。
hihocoder 1077 （单点更新，求区间内的最小值）
输入
每一个測试点（输入文件）有且仅有一组測试数据。
每组測试数据的第1行为一个整数N，意义如前文所述。
每组測试数据的第2行为N个整数。分别描写叙述每种商品的重量，当中第i个整数表示标号为i的商品的重量weight_i。
每组測试数据的第3行为一个整数Q，表示小Hi总共询问的次数与商品的重量被更改的次数之和。
每组測试数据的第N+4~N+Q+3行，每行分别描写叙述一次操作，每行的开头均为一个属于0或1的数字，分别表示该行描写叙述一个询问和描写叙述一次商品的重量的更改两种情况。
对于第N+i+3行，假设该行描写叙述一个询问，则接下来为两个整数Li, Ri。表示小Hi询问的一个区间[Li, Ri]。假设该行描写叙述一次商品的重量的更改，则接下来为两个整数Pi。Wi。表示位置编号为Pi的商品的重量变更为Wi
对于100%的数据，满足N<=10^6，Q<=10^6, 1<=Li<=Ri<=N。1<=Pi<=N, 0<weight_i, Wi<=10^4。
输出
对于每组測试数据，对于每一个小Hi的询问，依照在输入中出现的顺序，各输出一行，表示查询的结果：标号在区间[Li, Ri]中的全部商品中重量最轻的商品的重量。
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxn=1000005;
const int inf=0x3f3f3f3f;
struct SegTree
{
int l,r;
int MIN;
}segTree[maxn<<2];
void Build(int i,int l,int r)
{
segTree[i].l=l;segTree[i].r=r;
if(segTree[i].l==segTree[i].r)
{
scanf("%d",&segTree[i].MIN);
return;
}
int mid=(l+r)>>1;
Build(i<<1,l,mid);
Build((i<<1)|1,mid+1,r);
segTree[i].MIN=min(segTree[(i<<1)].MIN,segTree[(i<<1)|1].MIN);
}
void Update(int i,int p,int x)
{
if(segTree[i].l==segTree[i].r)
{
segTree[i].MIN=x;
return;
}
int l=segTree[i].l;
int r=segTree[i].r;
int mid=(l+r)>>1;
if(p<=mid)
Update(i<<1,p,x);
else
Update((i<<1)|1,p,x);
segTree[i].MIN=min(segTree[(i<<1)].MIN,segTree[(i<<1)|1].MIN);
}
int query(int i,int l,int r)
{
if(segTree[i].l==l&&segTree[i].r==r)
{
return segTree[i].MIN;
}
int ans=inf;
int mid=(segTree[i].l+segTree[i].r)>>1;
if(r<=mid)
ans=min(ans,query((i<<1),l,r));
else if(l>mid)
ans=min(ans,query((i<<1)|1,l,r));
else
ans=min(query(i<<1,l,mid),query((i<<1)|1,mid+1,r));
return ans;
}
int n,q;
int cm;
int l,r,p,x;
int main()
{
scanf("%d",&n);
Build(1,1,n);
scanf("%d",&q);
while(q--)
{
scanf("%d",&cm);
if(cm==0)
{
scanf("%d%d",&l,&r);
printf("%d
",query(1,l,r));
}
else
{
scanf("%d%d",&p,&x);
Update(1,p,x);
}
}
return 0;
}