地址：
题意：给n个数字。m次操作，每次操作更新一个数字或者查询区间最大值。
mark：典型线段树题。不过a的时候学了一下树状数组求区间最值。感觉对树状数组的理解又深刻了一点。不过这个更新不是O(lgn)而是O(lgn*lgn)的，比线段树慢！
代码：
线段树：
1 # include2 # include 3 4 5 #define max(a,b) (a>b?a:b) 6 int n ; 7 int tr[200010<<2] ; 8 9 10 void u(int a, int b, int l, int r, int rt)11 { 12 int m = (l+r)/2 ;13 if (l == r) {14 tr[rt] = b;15 return;16 }17 if (a <= m) u(a, b, l, m, rt*2);18 else u(a, b, m+1, r, rt*2+1);19 tr[rt] = max(tr[rt*2], tr[rt*2+1]);20 }21 22 23 int q(int a, int b, int l, int r, int rt)24 {25 int m = (l + r) / 2, a1, a2 ;26 if (a == l && b == r) return tr[rt];27 if (b <= m) return q(a, b, l, m, rt*2) ;28 else if (a > m) return q(a, b, m+1, r, rt*2+1) ;29 a1 = q(a, m, l, m, rt*2), a2 = q(m+1, b, m+1, r, rt*2+1) ;30 return max(a1, a2) ;31 }32 33 34 int main ()35 {36 int m, i, a, b ;37 char op[5] ;38 39 while (~scanf ("%d%d", &n, &m))40 {41 //memset (tr, 0, sizeof(tr));42 for (i = 1 ; i <= n ; i++)43 scanf ("%d", &a), u(i, a, 1, n, 1);44 while (m--)45 {46 scanf ("%s %d %d", op, &a, &b) ;47 if (op[0] == 'U') u(a, b, 1, n, 1);48 else printf ("%d\n", q(a, b, 1, n, 1)) ;49 }50 }51 return 0 ;52 }
树状数组（不加inline优化max函数的话会TLE！！！）
1 # include2 # include 3 4 5 int n, num[200010], tr[200010]; 6 int lowbit(int x){ return x & -x;} 7 inline int max(int a, int b){ return a>b?a:b;} 8 9 10 void u(int a, int b){11 int i, j;12 num[a] = b;13 for (i = a; i <= n; i+=lowbit(i))14 {15 tr[i] = num[i];16 for (j = 1; j < lowbit(i); j <<= 1)17 tr[i] = max(tr[i], tr[i-j]);18 }19 }20 21 22 int q(int a, int b){23 int i = b, ans = num[b];24 while (i >= a)25 if (i-lowbit(i)+1 >= a)26 ans = max(ans, tr[i]), i -= lowbit(i);27 else28 ans = max(ans, num[i]), i--;29 return ans;30 }31 32 33 int main ()34 {35 int a, b, i, m;36 char op[5];37 while (~scanf ("%d%d", &n, &m))38 {39 memset(tr, 0, sizeof(tr));40 for (i = 1; i <= n; i++)41 scanf ("%d", &a), u(i, a);42 while (m--)43 {44 scanf ("%s %d %d", op, &a, &b);45 if (op[0] == 'U') u(a, b);46 else printf ("%d\n", q(a, b)) ;47 }48 }49 return 0 ;50 }