第一次学线段树，从头到尾敲了快一小时。
其实add和sub是没必要写的，不过想想反正当练手，就敲上去了。
1 #include <stdio.h>
2 #include <string.h>
3 #include <malloc.h>
4
5 typedef struct Seg_Tree{
6 int left,right;
7 int amount;
8 struct Seg_Tree *lChild, *rChild;
9 }SegTreeNode,* SegTree;
10
11 SegTree createSegTree(int left, int right){
12 SegTree root;
13 if(right < left)
14 return NULL;
15 root = (SegTree) malloc (sizeof(SegTreeNode));
16 root->left = left;
17 root->right = right;
18 root->amount = 0;
19 if(right - left >= 1){
20 root->lChild = createSegTree(left, (left + right) / 2);
21 root->rChild = createSegTree((left + right) / 2 + 1, right);
22 }
23 else{
24 root->lChild = NULL;
25 root->rChild = NULL;
26 }
27 return root;
28 }
29
30 void InsertSegTree(SegTree root, int insertNum, int insertAmount){
31 SegTree p;
32 p = root;
33 if(p->left <= insertNum && p->right >= insertNum){
34 p->amount += insertAmount;
35 if(p->lChild != NULL)
36 InsertSegTree(p->lChild, insertNum, insertAmount);
37 if(p->rChild != NULL)
38 InsertSegTree(p->rChild, insertNum, insertAmount);
39 }
40 }
41
42 int Query(SegTree root, int left, int right){
43 SegTree p;
44 int mid,ans;
45 p = root;
46 ans = 0;
47 mid = (p->left + p->right) / 2;
48 if(p->left == left && p->right == right)
49 return p->amount;
50 else if(right <= mid)
51 ans = Query(p->lChild, left, right);
52 else if(left >= mid + 1)
53 ans = Query(p->rChild, left, right);
54 else {
55 ans = Query(p->lChild, left, mid);
56 ans += Query(p->rChild, mid+1, right);
57 }
58 return ans;
59 }
60
61 void Add(SegTree root,int addNum, int addAmount){
62 SegTree p;
63 int mid;
64 p = root;
65 mid = (p->left + p->right) / 2;
66 if(p->left <= addNum && p->right >= addNum){
67 p->amount += addAmount;
68 if(p->lChild != NULL && p->left <= addNum && addNum <= mid)
69 Add(p->lChild, addNum, addAmount);
70 else if(p->rChild != NULL && p->right >= addNum && addNum >= mid + 1)
71 Add(p->rChild, addNum, addAmount);
72 }
73 }
74
75 void Sub(SegTree root, int subNum, int subAmount){
76 SegTree p;
77 int mid;
78 p = root;
79 mid = (p->left + p->right) / 2;
80 if(p->left <= subNum && p->right >= subNum){
81 p->amount -= subAmount;
82 if(p->lChild != NULL && p->left <= subNum && subNum <= mid)
83 Sub(p->lChild, subNum, subAmount);
84 else if(p->rChild != NULL && p->right >= subNum && subNum >= mid + 1)
85 Sub(p->rChild, subNum, subAmount);
86 }
87 }
88 int main (void){
89 SegTree root;
90 int t,N,i,amount,left,right,casen=0;
91 char mission[10];
92 scanf("%d",&t);
93 while(t--){
94 casen++;
95 scanf("%d",&N);
96 root = createSegTree(1,N);
97 for(i = 1; i <= N; i++){
98 scanf("%d",&amount);
99 InsertSegTree(root, i, amount);
100 }
101 printf("Case %d:\n",casen);
102 while(scanf("%s",mission)){
103 if(!strcmp(mission,"End"))
104 break;
105 scanf("%d%d",&left,&right);
106 if(!strcmp(mission, "Query"))
107 printf("%d\n",Query(root, left, right));
108 else if(!strcmp(mission, "Add"))
109 Add(root, left, right);
110 else if(!strcmp(mission, "Sub"))
111 Sub(root, left, right);
112 }
113 }
114 return 0;
115 }