第二个线段树，用malloc申请果断超内存，自己写了个销毁树的函数果断超时。
最后还是默默地用数组实现了。
1 #include <stdio.h>
2
3 typedef struct{
4 int left,right,max;
5 int lChild,rChild;
6 }SegTree;
7 SegTree list[800000];
8
9 int max(int a, int b){
10 return a > b? a:b;
11 }
12 void createSegTree(int root, int left, int right){
13 int mid;
14 if(right < left)
15 return;
16 list[root].left = left;
17 list[root].right = right;
18 list[root].max = 0;
19 mid = (left + right) / 2;
20 if(right - left >= 1){
21 list[root].lChild = root << 1;
22 list[root].rChild = (root << 1) + 1;
23 createSegTree(list[root].lChild, left, mid);
24 createSegTree(list[root].rChild, mid + 1, right);
25 }
26 else{
27 list[root].lChild = -1;
28 list[root].rChild = -1;
29 }
30 }
31
32 void updateSegTree(int root, int updateNum, int score){
33 int mid;
34 mid = (list[root].left + list[root].right) / 2;
35 if(list[root].left <= updateNum && updateNum <= list[root].right){
36 list[root].max = max(list[root].max, score);
37 if(list[root].lChild != -1 && updateNum <= mid)
38 updateSegTree(list[root].lChild, updateNum, score);
39 else if(list[root].rChild != -1 && updateNum >= mid + 1)
40 updateSegTree(list[root].rChild, updateNum, score);
41 }
42 }
43
44 int queryHighestScore(int root, int left, int right){
45 int mid,ans;
46 mid = (list[root].left + list[root].right) / 2;
47 if(list[root].left == left && list[root].right == right)
48 return list[root].max;
49 else if(list[root].lChild != -1 && right <= mid)
50 ans = queryHighestScore(list[root].lChild, left, right);
51 else if(list[root].rChild != -1 && left >= mid + 1)
52 ans = queryHighestScore(list[root].rChild, left, right);
53 else{
54 ans = queryHighestScore(list[root].lChild,left, mid);
55 ans = max(ans, queryHighestScore(list[root].rChild, mid + 1, right));
56 }
57 return ans;
58 }
59
60 int main (void){
61 char order;
62 int i,N,M,score,left,right,root;
63 // freopen("in.txt","r",stdin);
64 while(~scanf("%d%d",&N,&M)){
65 root = 1;
66 createSegTree(root,1,N);
67 for(i = 1; i <= N; i++){
68 scanf("%d",&score);
69 updateSegTree(root, i, score);
70 }
71 getchar();
72 for(i = 0; i < M; i++){
73 scanf("%c%d%d",&order,&left,&right);
74 getchar();
75 if(order == 'Q')
76 printf("%d\n",queryHighestScore(root, left, right));
77 else
78 updateSegTree(root, left, right);
79 }
80 }
81 return 0;
82 }