hdu1754，线段树（模板题）

#include <bits/stdc++.h>

using namespace std;

struct Node{  int value;  int left,right;
};
const int N=200005;
Node node[4*N];
int father[N];
int n,m,g;
string op;
int a,b;

void buildTree(int i,int l,int r){  node[i].left=l;  node[i].right=r;  node[i].value=0;  if(l==r){  father[l]=i;  return;  }  buildTree(i*2,l,(l+r)/2);//如果用位运算，位运算优先级比四则运算低  buildTree(i*2+1,(l+r)/2+1,r);
}

void upData(int ri){  if(ri==1) return;  int fi=ri/2;  int a=node[fi*2].value,  b=node[fi*2+1].value;  node[fi].value=max(a,b);  upData(ri/2);
}

int Max;
void query(int i,int l,int r){  if(l==node[i].left&&r==node[i].right){  Max=max(node[i].value,Max);  return;  }    i*=2;  if(l<=node[i].right){//不用管l<node[i].left情况，这个情况会被切到左边的同级，现在只管 node[i.left到node[i.right的情况  if(r<=node[i].right) query(i,l,r);  else query(i,l,node[i].right);  }  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 argc, char** argv) {  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;  upData(father[i]);  }    for(int i=1;i<=m;i++){  cin>>op>>a>>b;  if(op[0]=='Q'){  Max=0;  query(1,a,b);cout<<Max<<endl;  }else{  node[father[a]].value=b;  upData(father[a]);  }  }  }  return 0;
}