Input
多组数据输入
每组数据第一行为一个整数n(n<=100000)，表示小明记录数据的个数。
接下来有一行有n个整数，表示小明一开始记录的数据。
第三行为一个整数m(M<50000)，表示xiaoming和朋友对话的次数。
接下来的m行，表示对话的动作，有两种格式。
change i num 表示小明记录错误，应该把第i个数据变成num,同一个数据有可能被改变多次。
ask i j 表示朋友在询问从第i个数据到第j个数据的和。
Output
对于第N组数据，你需要先输出Case N：
对于每一次ask，你只需要输出结果。
Sample Input
4
3 2 3 1
5
ask 2 3
change 2 1
ask 2 3
change 3 1
ask 2 4
Sample Output
Case 1:
5
4
3
View Code
1 #include "iostream"
2 #include <cstdio>
3 #define MAX 100005
4 #define lc(x) ((x)<<1)
5 #define rc(x) (((x)<<1)+1)
6 using namespace std;
7 struct node
8 {
9 int l,r,m;
10 };
11 int score[MAX];
12 node tree[MAX*3];
13 int p,q;
14 char cmd[10];
15 int build(int l,int r,int i)//从下到上建树
16 {
17 tree[i].l=l;
18 tree[i].r=r;
19 if(l==r)
20 {
21 tree[i].m=score[l];
22 return 0;
23 }
24 int mid=(l+r)>>1;
25 build(l,mid,lc(i));//左儿子节点
26 build(mid+1,r,rc(i));//右儿子节点
27 tree[i].m=tree[lc(i)].m+tree[rc(i)].m;//父亲节点是其左右儿子之和
28 return 0;
29 }
30
31 int renew(int i ,int num, int newv)//从下向上更新树
32 {
33 if(tree[i].r==num&&tree[i].l==num)
34 tree[i].m=newv;
35 else
36 {
37 if(num<=tree[lc(i)].r)
38 renew(lc(i),num,newv);
39 else
40 renew(rc(i),num,newv);
41 tree[i].m=tree[lc(i)].m+tree[rc(i)].m;
42 }
43 return 0;
44 }
45 int ans;
46 void finds(int a,int b,int i)//查找
47 {
48 if(a<=tree[i].l&&tree[i].r<=b)
49 ans+=tree[i].m;
50 else
51 if(b<=tree[lc(i)].r)
52 finds(a,b,lc(i));
53 else
54 if(a>=tree[rc(i)].l)
55 finds(a,b,rc(i));
56 else
57 {
58 finds( a,tree[lc(i)].r,lc(i) );
59 finds( tree[rc(i)].l,b,rc(i) );
60 }
61 }
62
63 int main()
64 {
65 int n,i,m,t=1;
66 while(scanf("%d",&n)!=EOF)
67 {
68 for(i=1;i<=n;i++)
69 scanf("%d",&score[i]);
70 printf("Case %d:\n",t++);
71 build(1,n,1);
72 scanf("%d",&m);
73 for(i=1;i<=m;i++)
74 {
75 scanf("%s %d %d",cmd,&p,&q);
76 if(cmd[0]=='a')
77 {
78 ans=0;
79 finds(p,q,1);
80 printf("%d\n",ans);
81 }
82 else if(cmd[0]=='c')
83 renew(1,p,q);
84 }
85 }
86 return 0;
87 }