题目：点击打开题目链接

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 5

Sample  Output：

5
6
5
9

思路：这道题可以用树状数组、线段树都可以，都是单点更新，区间求最大值的过程。

其中用树状数组方法时需要注意查询的过程，要活用查询操作。从R开始查询，然后通过R - lowbit [ R ] 进行一个区间一个区间的查询来减少时间复杂度，但是如果要查询的区间的左界比L小，就只对此单点进行查询，再进行下一个区间的查询，直到查询到L的位置。

下面是2种方法的代码。

My  DaiMa（树状数组）：

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
int a[200005],build[200005],lowbit[200005],n;
//lowbit[i]表示i所管辖的数有多少个，也是i的二进制中从右往左第一个1的位置
void GetLowbit()
{
    for(int i = 1; i <= n ; i++)
        lowbit[i] = i&(-i);//-x为x的补码
}
///建树，先求出每一段的初始最大值存在build数组里
void TreeBuild()
{
    for(int i = 1; i <= n; i++)
    {
        build[i] = a[i];
        for(int j = i-1; j > i-lowbit[i]; j--)
            build[i] = max(build[i],a[j]);
    }
}
///单点更新，更新所有管辖到x的build值
void update(int x, int y)
{
    a[x] = y;
    for(int i = x; i <= n; i += lowbit[i])
        build[i] = max(build[i],a[x]);
}
///查询
int Find_max(int x,int y)
{
    int maxx = a[y];///从区间右边开始
    while(y != x)
    {
        for(y -= 1; y-lowbit[y] > x; y -= lowbit[y])///根据lowbit进行一个区间一个区间的查询
            maxx = max(maxx,build[y]);
        maxx = max(maxx,a[y]);///当查询的区间的左界小于x时，只对单点进行查询
    }
    return maxx;
}
int main()
{
    int m;
    char ch;
    while(cin >> n >> m)
    {
        for(int i = 1; i <= n; i++)
            scanf("%d",&a[i]);
        GetLowbit();
        TreeBuild();
        int x,y;
        while(m--)
        {
            cin >> ch >> x >> y;
            if(ch == 'U') update(x,y);///单点更新
            else cout << Find_max(x,y) << endl;///查询区间最大值
        }
    }
}

My  DaiMa（线段树）：

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<algorithm>
#include<queue>
#include<math.h>
#include<set>
#include<time.h>
#pragma GCC optimize(2)
using namespace std;
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
const int N = 200000;
struct Node
{
    int left,right,data;
}node[4*N];

///更新当前节点
void push_up(int root)
{
    node[root].data = max(node[root<<1].data , node[root<<1|1].data);
}

///构建线段树
void build(int root,int left,int right)
{
    node[root].left = left;
    node[root].right = right;
    if(left == right)
    {
        scanf("%d",&node[root].data);
        return;
    }
    int mid = (left+right)/2;
    build(root<<1,left,mid);///构建左子树
    build(root<<1|1,mid+1,right);///构建右子树
    push_up(root);
}

///单点更新
void update(int root,int a,int b)
{
    if(node[root].left == node[root].right && node[root].left == a)
    {
        node[root].data = b;
        return;
    }
    int mid = (node[root].left+node[root].right)/2;
    if(a <= mid) update(root<<1 , a , b);///更新的点在左子树中
    else update(root<<1|1 , a , b);///更新的点在右子树中
    push_up(root);
}

///区间查询
int query(int l,int r,int root)
{
    if(node[root].left == l && r == node[root].right)
        return node[root].data;
    int mid = (node[root].left+node[root].right)/2;
    if(r <= mid)///说明区间在左子树中
        query(l , r , root<<1);
    else if(mid+1 <= l)///说明区间在右子树中
        query(l, r, root<<1|1);
    else ///说明区间一部分在左子树中，一部分在右子树中，因此劈两半，两边都得查询，取最大值
    {
        int x = query(l, mid, root<<1);///注意这里是mid，而不是r，因为区间被劈了两半
        int y = query(mid+1, r, root<<1|1);
        return max(x,y);
    }
}
int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        build(1, 1, n);
        char ch;
        int a,b;
        while(m--)
        {
            cin >> ch >> a >>b;
            if(ch == 'U')
                update(1, a, b);
            else
            {
                int ans = query(a, b, 1);
                printf("%d\n",ans);
            }
        }
    }
}