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

解析：
题意很简单，写个单点修改的线段树就好了，然后为了熟悉树状数组的操作，又多学习了下树状数组求区间最大值的写法。

idx [ i ] 表示 区间中最大的值，a [ ] 是存放元素数组

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second

typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
const ll mod=1000000007;
const int maxn=2e5+10;
const int inf=0x3f3f3f3f;
const double eps=1e-6;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

int t,n,m,x,y,cnt=0;
int a[maxn],idx[maxn];
int lowbit(int x){
   return x&-x;
}
void modify(int p,int v){
   a[p] = v;
   for(int i = p; i <= n; i+=lowbit(i)){
      if(idx[i] < v) idx[i] = v;
      else break;
      for(int j = 1; j < lowbit(i); j<<=1){
         idx[i] = max(idx[i],idx[i-j]);
      }
   }
}
 
int query(int l,int r){
   int ans = a[r];
 
   while(true){
      ans = max(a[r],ans);
      if(l == r)break;
      for(r--; r-lowbit(r) >= l; r -= lowbit(r)){
         ans = max(ans,idx[r]);
      }
   }
   return ans;
}

int main(){
   while(~scanf("%d %d",&n,&m) && n){
      memset(idx,0,sizeof idx);
      for(int i=1;i<=n;i++){
         scanf("%d",&a[i]);
         modify(i,a[i]);
      }
      while(m--){
         char str[2];
         scanf("%s %d %d",str,&x,&y);
         if(str[0] == 'Q') printf("%d\n",query(x,y));
         else modify(x,y);
      }
   }
   return 0;
}

同时，放上单点修改的线段树的写法：

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
const ll mod=1000000007;
const int maxn=2e6+10;
const int inf=0x3f3f3f3f;
const double eps=1e-6;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
int t,n,m,a,b;
int sum[maxn<<2];
void push_up(int rt){
	sum[rt] = max(sum[rt<<1],sum[rt<<1 | 1]);
}
void build(int l,int r,int rt){
	if(l == r) {
		scanf("%d",&sum[rt]);
		return;
	}
	int mid =(l+r)>>1;
	build(lson);
	build(rson);
	push_up(rt);
}
void update(int p,int add,int l,int r,int rt){
	if(l==r){
		sum[rt]=add;
		return;
	}
	int mid=(l+r)>>1;
	if(p<=mid) update(p,add,lson);
	else update(p,add,rson);
	push_up(rt);
}
int query(int a,int b,int l,int r,int rt){
	if(a<=l && b>=r) return sum[rt];
	int mid = (l+r)>>1;
	int ans=0;
	if(a<=mid) ans=max(ans,query(a,b,lson));
	if(b>mid) ans=max(ans,query(a,b,rson));
	return ans;
}

int main(){
	while(~scanf("%d %d",&n,&m) && n){
		build(1,n,1);
		while(m--){
			char str[2];
			scanf("%s %d %d",str,&a,&b);
			if(str[0] == 'Q') printf("%d\n",query(a,b,1,n,1));
			else update(a,b,1,n,1);
		}
	}

	
	return 0;
}