首先，线段树，你细品……
em……
首先，线段树的作用是神马？
就是找一个区间内的最大值。
“那不是有手就行？”
但是，要替换！
就像这道非常BT的1.1.1例题：
在N（1<=N<=100000）个数A1…An组成的序列上进行M(1<=M<=100000)次操作，操作有两种：
(1)1 x y：表示修改A[x]为y；
(1)2 x y：询问x到y之间的最大值。
输入
第一行输入N(1<=N<=100000)，表示序列的长度，接下来N行输入原始序列；接下来一行输入M(1<=M<=100000)表示操作的次数，接下来M行，每行为1 x y或2 x y
输出
对于每个操作(2)输出对应的答案。
样例输入
5
1
2
3
4
5
3
2 1 4
1 3 5
2 2 4
样例输出
4
5
还好，但是看看数据范围：
第一行输入N(1<=N<=100000)，表示序列的长度，接下来N行输入原始序列；接下来一行输入M(1<=M<=100000)表示操作的次数，接下来M行，每行为1 x y或2 x y
还有手就行吗？
所以我们就要学习线段树，在此基础上加上修改操作的算法。
由于我是一名低IQ用户，所以这里就讲解一下最适合新手的做法。
1.建树
线段树就是一棵二叉树，每一个节点存储的是l(left)~r(right)里的最大值。
首先，线段树的存储方式肯定得是一维数组，所以我们就可以通过一位数组的每一个下标求出当前节点的l和r，直至l=r，然后我们就令：
if(l==r){
a[i].maxn=b[l];//a是线段树，b是我们输入的数组
return ;
}
然后其他的操作自然就是大名鼎鼎，宇宙无敌，举世无双，超级无敌牛逼的
二分查找！
别再问我二分查找是什么，快速排序总知道吧…
然而我们该怎么确定一个不是最底层节点的最大值呢？
仔细观察然后细品，然后就发现：
父亲节点=两个儿子节点的最大值！
a[i].maxn=max(a[2*i].maxn,a[2*i+1].maxn);
所以这里我们就完成了建树部分：
建树部分代码
//a数组存储的是线段树，b数组是输入的数组。
void make(int l,int r,int i){
if(l==r){
a[i].maxn=b[l];
return ;
}
int m=(l+r)/2;
make(l,m,2*i);
make(m+1,r,2*i+1);
a[i].maxn=max(a[2*i].maxn,a[2*i+1].maxn);
}
2.修改
修改操作是最难理解的，但是我可以把它讲的很简单。
首先，我们肯定是修改一个值，就是修改：
用脚趾头想想都知道：
对于一个修改的数，跟着要变化的还有他的父亲，他的爷爷，他的祖宗十八代……直到根节点
哦！！
其实就是下去上来走一遭！
首先我们找到要更改的子节点，接下来我们找到他的父亲节点，并且看看会不会影响到他的值；然后再找到爸爸的爸爸节点，看看会不会影响到他的最大值…直到我们找到根节点，看看会不会影响他的最大值，时间复杂度为
O（log2(n)）：
修改部分代码：
void add(int i,int l,int r){
if(l==r){a[i].maxn=y;return ;}//如果找到了要修改的点，那么就修改一下（y是修改值）
int m=(l+r)/2;
if(x<=m) add(i*2,l,m);
else add(i*2+1,m+1,r);
a[i].maxn=max(a[i*2].maxn,a[i*2+1].maxn);//如果不是底层节点，那么它就＝两个儿子的最大值
}
3.查询
查询操作就是查找一段里面的最大值，但是我们知道，一个一个查找太耗费时间了，线段树就是帮助我们节省时间的！
这下总该听懂了吧 !
所以说这个算法的好处就在于我们没必要每次都去一个一个查找最大值，只需要一段一段的去查找，就相当于把若干个点压缩成了一段，如果压缩成的这一段在我们的查找范围内，那么就不必再继续查找下去，只需要跟这一段取最大值就行了！
查询部分代码
//x是查找段的左端点，y是查找段的右端点
void qry(int i,int l,int r){
if(r<x||l>y) return ;
if(l>=x&&r<=y){ans=max(ans,a[i].maxn); return ;}
int m=(l+r)/2;
qry(i*2,l,m);
qry(i*2+1,m+1,r);
}
AC代码（抄袭党看这边！）
我们把这三个函数结合起来，再加上主函数的一顿操作，就可以得到正确代码（金色传说！）：
#include<bits/stdc++.h>
using namespace std;
int x,y,ans,n,m,ph,b[1000000];
struct node{
int maxn;
}a[1000000];
int max(int x,int y){return x>y?x:y;}
void make(int l,int r,int i){
if(l==r){
a[i].maxn=b[l];
return ;
}
int m=(l+r)/2;
make(l,m,2*i);
make(m+1,r,2*i+1);
a[i].maxn=max(a[2*i].maxn,a[2*i+1].maxn);
}
void qry(int i,int l,int r){
if(r<x||l>y) return ;
if(l>=x&&r<=y){ans=max(ans,a[i].maxn); return ;}
int m=(l+r)/2;
qry(i*2,l,m);
qry(i*2+1,m+1,r);
}
void add(int i,int l,int r){
if(l==r){a[i].maxn=y;return ;}
int m=(l+r)/2;
if(x<=m) add(i*2,l,m);
else add(i*2+1,m+1,r);
a[i].maxn=max(a[i*2].maxn,a[i*2+1].maxn);
}
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
make(1,n,1);
scanf("%d",&m);
for(int i=1;i<=m;i++){
ans=0;
scanf("%d%d%d",&ph,&x,&y);
if(ph==2){qry(1,1,n);printf("%d\n",ans);}
else add(1,1,n);
}
return 0;
}
结尾
最后的最后，如果你弄懂了线段树，那就一键三连，下一期估计我会发网络流题解。
呵呵o(￣︶￣)o，怎么可能，肯定先拖更一个月！