I Hate It!（线段树-超详细~）- HDU 1754
作者：紫芝眉宇
很用心的一篇线段树文章哈~
Problem Description
很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。 这让很多学生很反感。 不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。
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 5Sample Output
5
6
5
9线段树三类问题：
①更新点，查询区间 ②更新区间，查询点 ③更新区间，查询区间
1.线段树是一种二叉搜索树，与区间树相似，它将一个区间划分为一些
单元区间，每个单元区间对应线段树的一个叶子节点。
线段树区间查询：询问某段区间某些性质，如极值、求和。 2.对于线段树中每一个非叶子节点[a,b], 它的左儿子表示的区间为[a,(a+b)/2]， 右儿子表示的区间为[(a+b)/2+1,b]。 3.线段树是平衡二叉树，最后的子节点数目为N，即整个线段区间长度。
4.使用线段树可以快速的查找某一个节点在若干条线段中出现的次数， 时间复杂度为O(logN),未优化的空间复杂度为2N，需要离散化让空间压缩。 5.线段树如何处理？ 若节点x（x为奇数）记录的是第一个点的数据，节点x+1记录的是第二个点 的数据，那么节点 x/2记录的就是[1,2]上的有效数据，以此类推，最顶端 的父节点记录的就是区间[1,n]上的有效数据，那么对于每个节点的数据 有且仅有 logn个节点的数据会被它影响到，因此每次跟新logn个点， 查询也一样，有效节约了时间。 6.对于每个节点，其代表的区间[x,y]之间的值， 左儿子节点代表的就是[x,(x+y)/2]区间的值， 右儿子节点代表的是区间[(x+y)/2+1,y]上的值，
既保证了无重复，由保证了树的层数最短，查询效率最高。
7.单点更新线段树 由于事先用 father[]数组保存过每个节点对应的下标，因此只需要 知道第几个点，就能知道这个点在结构体中的位置（即下标），
根据之前已知的基本关系，就只需要直接一路更新上去即可。
源代码：G++
#include<bits/stdc++.h>
using namespace std;
//const int MAXNODE=2097152;
const int MAX = 2e6 + 3;
const int MAXNODE = 1 << 19;
struct NODE {
int value;//节点对应区间的权值
int left, right; //区间[left,right]
} node[MAXNODE];
//当区间长度为 0时，对应一个点
int father[MAX];//每个点对应的结构体数组下标
//为区间[left,right]建立一个一个以 i 为祖先的线段树
//i为数组下标，即结点序号
void BuildTree(int i, int left, int right)
{
//写入第 i 个结点中的左区间
node[i].left = left;
//写入第 i 个结点中的右区间
node[i].right = right;
//每个区间初始化为 0
node[i].value = 0 ;
//当区间长度为 0 时，结束递归
if (left == right)
{
father[left] = i;
//能知道某个点对应的序号
//为了更新时，从下往上一直到顶
return;
}
//该结点往左孩子的方向继续建立线段树，
//线段树的划分是二分思想
//这里将区间 (left,right)一分为二
BuildTree(i << 1, left, (right + left) / 2);
//该结点往右孩子的方向，继续建立线段树
BuildTree(i << 1 | 1, (right + left) / 2 + 1, right);
}
//从下往上更新，这个点本身已经在函数外更新过
void UpdateTree(int ri)
{
//整个线段树的祖先结点对应的下标为 1
if (ri == 1) return; //向上已经找到了祖先
int fi = ri / 2; //ri的父结点
int a = node[fi << 1].value; //该父结点的两个孩子结点 （左）
int b = node[fi << 1 | 1].value; //右
//更新这个父结点，从两个孩子结点中挑个大的
node[fi].value = (a > b) ? a : b;
//递归更新，由父结点往上找
UpdateTree(ri >> 1);
}
int Max;
// i 为区间序号
//对应的区间是最大范围的那个区间，一般初始为 1
void query(int i, int l, int r)
{
//找到了一个完全重合的区间
if (node[i].left == l && node[i].right == r)
{
Max = max(Max, node[i].value);
return;
}
//get the left child of the tree node
i = i << 1;
if (l <= node[i].right) //左区间有涉及
{
if (r <= node[i].right) //全包含于左区间，则查询区间形态不变
query(i, l, r);
else//半包含于左区间，则查询区间拆分,左端点不变，右端点变为左孩子的右区间端点
query(i, l, node[i].right);
}
//right child of the tree
i++;
if (r >= node[i].left) { //右区间有涉及
if (l >= node[i].left) //全包含于右区间，则查询区间形态不变
query(i, l, r);
else//半包含于左区间，则查询区间拆分
query(i, node[i].left, r);
}
}
int main()
{
int n, m, g;
ios::sync_with_stdio(false);//关闭流同步
while (cin >> n >> m) {
BuildTree(1, 1, n);
for (int i = 1; i <= n; i++)
{
cin >> g;
node[father[i]].value = g;
UpdateTree(father[i]);
}
string op;
int a, b;
while (m--) {
cin >> op >> a >> b;
if (op[0] == 'Q') {
Max = 0;
query(1, a, b);
cout << Max << endl;
} else {
node[father[a]].value = b;
UpdateTree(father[a]);
}
}
}
return 0;
}腾讯云开发者
