题意：
输入一行数字，查询第i个数到第j个数之间的最大值。可以修改其中的某个数的值。
输入：
包含多组输入数据。
每组输入首行两个整数n，m。表示共有n个数，m次操作。
接下来一行包含n个整数。
接下来m行，每行包含一个字母s，两个整数a，b。
当s为’Q’，表示查询第a个数到第b个数之间的最大值。
当s为’U’，表示将第a个数更改为b。
输出：
每次查询输出一个结果，每次输出占一行。
题解：
点修改区间求最值，可以用树状数组模板。
具体见代码——
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std; const int N = ; int a[N], c[N];
int t, n, m; int lowbit(int x)
{
return x&(-x);
} void Maxn(int x, int y)
{
a[x] = y;
for(int i = x; i <= n; i += lowbit(i)) //需要修改的c[]
{
c[i] = y;
for(int j = ; j < lowbit(i); j <<= ) //修改时需要比较的c[]
{
c[i] = c[i] > c[i-j] ? c[i] : c[i-j];
}
}
} void Init()
{
int y;
memset(c, , sizeof(c));
for(int i = ; i <= n; i++)
{
scanf("%d", &y);
a[i] = y;
c[i] = y;
for(int j = ; j <lowbit(i); j <<= ) //需要比较的c[]
c[i] = c[i] > c[i-j] ? c[i] : c[i-j];
}
} void Query(int l, int r)
{
int ans = ;
while()
{
ans = ans > a[r] ? ans : a[r];
if(r == l) break;
for(r -= ; r-l >= lowbit(r); r -= lowbit(r))
ans = ans > c[r] ? ans : c[r];
}
printf("%d\n", ans);
} void Work()
{
char s[];
int x, y;
for(int i = ; i <= m; i++)
{
scanf("%s%d%d", s, &x, &y);
if(s[] == 'U') Maxn(x, y);
else if(s[] == 'Q') Query(x, y);
}
} int main()
{
//freopen("test.in", "r", stdin);
while(~scanf("%d%d", &n, &m))
{
Init();
Work();
}
}
树状数组区间求最值模板——