hdu 1754 I Hate It（线段树 + 详细注释）
很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。
这让很多学生很反感。
不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。
Input
本题目包含多组测试，请处理到文件结束。
在每个测试的第一行，有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 )，分别代表学生的数目和操作的数目。
学生ID编号分别从1编到N。
第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取'Q'或'U') ，和两个正整数A，B。
当C为'Q'的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。
当C为'U'的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。
Output
对于每一次询问操作，在一行里面输出最高成绩。
Sample Input
5 6 1 2 3 4 5 Q 1 5 U 3 6 Q 3 4 Q 4 5 U 2 9 Q 1 5
Sample Output
5
6
5
9
Hint
Huge input,the C function scanf() will work better than cin
这里我们先学习一下数据结构中的线段树。
关于线段树的理解参加博客https://www.cnblogs.com/TenosDoIt/p/3453089.html ，我借用一下。
一步一步理解线段树
--------------------------
线段树，类似区间树，它在各个节点保存一条线段（数组中的一段子数组），主要用于高效解决连续区间的动态查询问题，由于二叉结构的特性，它基本能保持每个操作的复杂度为O(logn)。
线段树的每个节点表示一个区间，子节点则分别表示父节点的左右半区间，例如父亲的区间是[a,b]，那么(c=(a+b)/2)左儿子的区间是[a,c]，右儿子的区间是[c+1,b]。
下面我们从一个经典的例子来了解线段树，问题描述如下:从数组arr[0...n-1]中查找某个数组某个区间内的最小值，其中数组大小固定，但是数组中的元素的值可以随时更新。
对这个问题一个简单的解法是：遍历数组区间找到最小值，时间复杂度是O(n),额外的空间复杂度O(1)。当数据量特别大，而查询操作很频繁的时候，耗时可能会不满足需求。
另一种解法：使用一个二维数组来保存提前计算好的区间[i,j]内的最小值，那么预处理时间为O(n^2)，查询耗时O(1), 但是需要额外的O(n^2)空间，当数据量很大时，这个空间消耗是庞大的，而且当改变了数组中的某一个值时，更新二维数组中的最小值也很麻烦。
我们可以用线段树来解决这个问题：预处理耗时O(n)，查询、更新操作O(logn)，需要额外的空间O(n)。根据这个问题我们构造如下的二叉树
- 叶子节点是原始组数arr中的元素
- 非叶子节点代表它的所有子孙叶子节点所在区间的最小值
例如对于数组[2, 5, 1, 4, 9, 3]可以构造如下的二叉树（背景为白色表示叶子节点，非叶子节点的值是其对应数组区间内的最小值，例如根节点表示数组区间arr[0...5]内的最小值是1）： 本文地址
由于线段树的父节点区间是平均分割到左右子树，因此线段树是完全二叉树，对于包含n个叶子节点的完全二叉树，它一定有n-1个非叶节点，总共2n-1个节点，因此存储线段是需要的空间复杂度是O(n)。那么线段树的操作：创建线段树、查询、节点更新 是如何运作的呢（以下所有代码都是针对求区间最小值问题）？
对于线段树我们可以选择和普通二叉树一样的链式结构。由于线段树是完全二叉树，我们也可以用数组来存储，下面的讨论及代码都是数组来存储线段树，节点结构如***意到用数组存储时，有效空间为2n-1,实际空间确不止这么多，比如上面的线段树中叶子节点1、3虽然没有左右子树，但是的确占用了数组空间，实际空间是满二叉树的节点数目： ，
是树的高度，但是这个空间复杂度也是O(n)的 ）。
struct SegTreeNode
{
int val;
}；
定义包含n个节点的线段树 SegTreeNode segTree[n]，segTree[0]表示根节点。那么对于节点segTree[i]，它的左孩子是segTree[2*i+1],右孩子是segTree[2*i+2]。
我们可以从根节点开始，平分区间，递归的创建线段树，线段树的创建函数如下：
const int MAXNUM = 1000;
struct SegTreeNode
{
int val;
}segTree[MAXNUM];//定义线段树
/*
功能：构建线段树
root：当前线段树的根节点下标
arr: 用来构造线段树的数组
istart：数组的起始位置
iend：数组的结束位置
*/
void build(int root, int arr[], int istart, int iend)
{
if(istart == iend)//叶子节点
segTree[root].val = arr[istart];
else
{
int mid = (istart + iend) / 2;
build(root*2+1, arr, istart, mid);//递归构造左子树
build(root*2+2, arr, mid+1, iend);//递归构造右子树
//根据左右子树根节点的值，更新当前根节点的值
segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
}
}已经构建好了线段树，那么怎样在它上面超找某个区间的最小值呢？查询的思想是选出一些区间，使他们相连后恰好涵盖整个查询区间，因此线段树适合解决“相邻的区间的信息可以被合并成两个区间的并区间的信息”的问题。代码如下，具体见代码解释
/*
功能：线段树的区间查询
root：当前线段树的根节点下标
[nstart, nend]: 当前节点所表示的区间
[qstart, qend]: 此次查询的区间
*/
int query(int root, int nstart, int nend, int qstart, int qend)
{
//查询区间和当前节点区间没有交集
if(qstart > nend || qend < nstart)
return INFINITE;
//当前节点区间包含在查询区间内
if(qstart <= nstart && qend >= nend)
return segTree[root].val;
//分别从左右子树查询，返回两者查询结果的较小值
int mid = (nstart + nend) / 2;
return min(query(root*2+1, nstart, mid, qstart, qend),
query(root*2+2, mid + 1, nend, qstart, qend));
}举例说明（对照上面的二叉树）：
1、当我们要查询区间[0,2]的最小值时，从根节点开始，要分别查询左右子树，查询左子树时节点区间[0,2]包含在查询区间[0,2]内，返回当前节点的值1，查询右子树时，节点区间[3,5]和查询区间[0,2]没有交集，返回正无穷INFINITE，查询结果取两子树查询结果的较小值1，因此结果是1.
2、查询区间[0,3]时，从根节点开始，查询左子树的节点区间[0,2]包含在区间[0,3]内，返回当前节点的值1；查询右子树时，继续递归查询右子树的左右子树，查询到非叶节点4时，又要继续递归查询：叶子节点4的节点区间[3,3]包含在查询区间[0,3]内，返回4，叶子节点9的节点区间[4,4]和[0,3]没有交集，返回INFINITE,因此非叶节点4返回的是min(4, INFINITE) = 4，叶子节点3的节点区间[5,5]和[0,3]没有交集，返回INFINITE,因此非叶节点3返回min(4, INFINITE) = 4, 因此根节点返回 min(1,4) = 1。
单节点更新是指只更新线段树的某个叶子节点的值，但是更新叶子节点会对其父节点的值产生影响，因此更新子节点后，要回溯更新其父节点的值。
/*
功能：更新线段树中某个叶子节点的值
root：当前线段树的根节点下标
[nstart, nend]: 当前节点所表示的区间
index: 待更新节点在原始数组arr中的下标
addVal: 更新的值（原来的值加上addVal）
*/
void updateOne(int root, int nstart, int nend, int index, int addVal)
{
if(nstart == nend)
{
if(index == nstart)//找到了相应的节点，更新之
segTree[root].val += addVal;
return;
}
int mid = (nstart + nend) / 2;
if(index <= mid)//在左子树中更新
updateOne(root*2+1, nstart, mid, index, addVal);
else updateOne(root*2+2, mid+1, nend, index, addVal);//在右子树中更新
//根据左右子树的值回溯更新当前节点的值
segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
}比如我们要更新叶子节点4（addVal = 6）,更新后值变为10，那么其父节点的值从4变为9，非叶结点3的值更新后不变，根节点更新后也不变。
区间更新是指更新某个区间内的叶子节点的值，因为涉及到的叶子节点不止一个，而叶子节点会影响其相应的非叶父节点，那么回溯需要更新的非叶子节点也会有很多，如果一次性更新完，操作的时间复杂度肯定不是O(lgn)，例如当我们要更新区间[0,3]内的叶子节点时，需要更新出了叶子节点3,9外的所有其他节点。为此引入了线段树中的延迟标记概念，这也是线段树的精华所在。
延迟标记：每个节点新增加一个标记，记录这个节点是否进行了某种修改(这种修改操作会影响其子节点)，对于任意区间的修改，我们先按照区间查询的方式将其划分成线段树中的节点，然后修改这些节点的信息，并给这些节点标记上代表这种修改操作的标记。在修改和查询的时候，如果我们到了一个节点p，并且决定考虑其子节点，那么我们就要看节点p是否被标记，如果有，就要按照标记修改其子节点的信息，并且给子节点都标上相同的标记，同时消掉节点p的标记。
因此需要在线段树结构中加入延迟标记域，本文例子中我们加入标记与addMark，表示节点的子孙节点在原来的值的基础上加上addMark的值，同时还需要修改创建函数build 和 查询函数 query，修改的代码用红色字体表示，其中区间更新的函数为update，代码如下：
const int INFINITE = INT_MAX;
const int MAXNUM = 1000;
struct SegTreeNode
{
int val;
int addMark;//延迟标记
}segTree[MAXNUM];//定义线段树
/*
功能：构建线段树
root：当前线段树的根节点下标
arr: 用来构造线段树的数组
istart：数组的起始位置
iend：数组的结束位置
*/
void build(int root, int arr[], int istart, int iend)
{
segTree[root].addMark = 0;//----设置标延迟记域
if(istart == iend)//叶子节点
segTree[root].val = arr[istart];
else
{
int mid = (istart + iend) / 2;
build(root*2+1, arr, istart, mid);//递归构造左子树
build(root*2+2, arr, mid+1, iend);//递归构造右子树
//根据左右子树根节点的值，更新当前根节点的值
segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
}
}
/*
功能：当前节点的标志域向孩子节点传递
root: 当前线段树的根节点下标
*/
void pushDown(int root)
{
if(segTree[root].addMark != 0)
{
//设置左右孩子节点的标志域，因为孩子节点可能被多次延迟标记又没有向下传递
//所以是 “+=”
segTree[root*2+1].addMark += segTree[root].addMark;
segTree[root*2+2].addMark += segTree[root].addMark;
//根据标志域设置孩子节点的值。因为我们是求区间最小值，因此当区间内每个元
//素加上一个值时，区间的最小值也加上这个值
segTree[root*2+1].val += segTree[root].addMark;
segTree[root*2+2].val += segTree[root].addMark;
//传递后，当前节点标记域清空
segTree[root].addMark = 0;
}
}
/*
功能：线段树的区间查询
root：当前线段树的根节点下标
[nstart, nend]: 当前节点所表示的区间
[qstart, qend]: 此次查询的区间
*/
int query(int root, int nstart, int nend, int qstart, int qend)
{
//查询区间和当前节点区间没有交集
if(qstart > nend || qend < nstart)
return INFINITE;
//当前节点区间包含在查询区间内
if(qstart <= nstart && qend >= nend)
return segTree[root].val;
//分别从左右子树查询，返回两者查询结果的较小值
pushDown(root); //----延迟标志域向下传递
int mid = (nstart + nend) / 2;
return min(query(root*2+1, nstart, mid, qstart, qend),
query(root*2+2, mid + 1, nend, qstart, qend));
}
/*
功能：更新线段树中某个区间内叶子节点的值
root：当前线段树的根节点下标
[nstart, nend]: 当前节点所表示的区间
[ustart, uend]: 待更新的区间
addVal: 更新的值（原来的值加上addVal）
*/
void update(int root, int nstart, int nend, int ustart, int uend, int addVal)
{
//更新区间和当前节点区间没有交集
if(ustart > nend || uend < nstart)
return ;
//当前节点区间包含在更新区间内
if(ustart <= nstart && uend >= nend)
{
segTree[root].addMark += addVal;
segTree[root].val += addVal;
return ;
}
pushDown(root); //延迟标记向下传递
//更新左右孩子节点
int mid = (nstart + nend) / 2;
update(root*2+1, nstart, mid, ustart, uend, addVal);
update(root*2+2, mid+1, nend, ustart, uend, addVal);
//根据左右子树的值回溯更新当前节点的值
segTree[root].val = min(segTree[root*2+1].val, segTree[root*2+2].val);
}区间更新举例说明：当我们要对区间[0,2]的叶子节点增加2，利用区间查询的方法从根节点开始找到了非叶子节点[0-2]，把它的值设置为1+2 = 3，并且把它的延迟标记设置为2，更新完毕；当我们要查询区间[0,1]内的最小值时，查找到区间[0,2]时，发现它的标记不为0，并且还要向下搜索，因此要把标记向下传递，把节点[0-1]的值设置为2+2 = 4，标记设置为2，节点[2-2]的值设置为1+2 = 3，标记设置为2（其实叶子节点的标志是不起作用的，这里是为了操作的一致性），然后返回查询结果：[0-1]节点的值4；当我们再次更新区间[0,1]（增加3）时，查询到节点[0-1],发现它的标记值为2，因此把它的标记值设置为2+3 = 5，节点的值设置为4+3 = 7；
其实当区间更新的区间左右值相等时（[i,i]），就相当于单节点更新，单节点更新只是区间更新的特例。
求区间的最大值、区间求和等问题都是采用类似上面的延迟标记域。下面会通过acm的一些题目来运用一下线段树。
等待更新......
参考资料
GeeksforGeeks: http://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/
GeeksforGeeks: http://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/
懂得博客[数据结构之线段树]：http://dongxicheng.org/structure/segment-tree/
MetaSeed[数据结构专题—线段树]: http://blog.csdn.net/metalseed/article/details/8039326
NotOnlySuccess[完全版 线段树]: http://www.notonlysuccess.com/index.php/segment-tree-complete/
【版权声明】转载请注明出处：http://www.cnblogs.com/TenosDoIt/p/3453089.html
而这道题正是单点更新的板子题，代码注释写的很详细。
AC代码如下：
#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 200005
int num[maxn];
struct node
{
int maxx;
int left,right;
}tree[maxn*3];
//构建线段树
int build(int root,int left,int right)
{
//当前节点所表示的区间
tree[root].left=left;
tree[root].right=right;
//左右区间相同时，则此节点为叶子，max应储存对应某个学生的值
if(left==right)
{
return tree[root].maxx=num[left];
}
int mid=left+right>>1;
//递归建立左右子树，并从子树中获得最大值
int a=build(root<<1,left,mid);
int b=build(root<<1|1,mid+1,right);
return tree[root].maxx=max(a,b);
}
//从节点root开始，查找left和right之间的最大值
inline int find(int root,int left,int right)
{
//若此区间与root所管理的区间无交集
if(tree[root].left>right||tree[root].right<left)
return 0;
//若此区间包含root所管理的区间
if(left<=tree[root].left&&tree[root].right<=right)
return tree[root].maxx;
//若此区间与root所管理的区间部分相交
int a=find(2*root,left,right);
int b=find(2*root+1,left,right);
return max(a,b);
}
//更新pos点的值
inline int update(int root,int pos,int val)
{
//若pos不存在于root所管理的区间内
if(pos<tree[root].left||tree[root].right<pos)
return tree[root].maxx;
//若root正好是一个符合条件的叶子
if(tree[root].left==pos&&tree[root].right==pos)
return tree[root].maxx=val;
//else
int a=update(2*root,pos,val);
int b=update(2*root+1,pos,val);
tree[root].maxx=max(a,b);
return tree[root].maxx;
}
int main()
{
int n,m;
int x,y;
char c;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
build(1,1,n);
for(int i=1;i<=m;i++)
{
getchar();
scanf("%c%d%d",&c,&x,&y);
if(c=='Q')
printf("%d\n",find(1,x,y));
else
{
num[x]=y;
update(1,x,y);
}
}
}
return 0;
}