题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1166
用结构体做的 470+ms;
1 #include <cstdio> 2 #include <algorithm> 3 #include <iostream> 4 #include <cstdlib> 5 #include <queue> 6 #include <cmath> 7 #include <cstring> 8 9 using namespace std; 10 11 struct N 12 { 13 int z,y,data; 14 struct N *l,*r; 15 }; 16 17 struct N *creat() 18 { 19 struct N *p = (struct N *)malloc(sizeof(struct N)); 20 p->l = NULL; 21 p->r = NULL; 22 return p; 23 } 24 25 int st[50010]; 26 27 int change(int z,int y,struct N *root) 28 { 29 int m = (z+y)/2; 30 root->z = z; 31 root->y = y; 32 if(z == y) 33 { 34 root->data = st[z]; 35 return (st[z]); 36 } 37 root->l = creat(); 38 root->r = creat(); 39 int tl = change(z,m,root->l); 40 int tr = change(m+1,y,root->r); 41 root->data = (tl + tr); 42 return root->data; 43 } 44 45 void add(int site,int s,int z,int y,struct N *root) 46 { 47 int m = (z+y)/2; 48 49 if(z == y) 50 { 51 root->data += s; 52 return; 53 } 54 55 if(site <= m) 56 { 57 add(site,s,z,m,root->l); 58 root->data += s; 59 } 60 else 61 { 62 add(site,s,m+1,y,root->r); 63 root->data += s; 64 } 65 } 66 67 void sub(int site,int s,int z,int y,struct N *root) 68 { 69 int m = (z+y)/2; 70 71 if(z == y) 72 { 73 root->data -= s; 74 return; 75 } 76 77 if(site <= m) 78 { 79 sub(site,s,z,m,root->l); 80 root->data -= s; 81 } 82 else 83 { 84 sub(site,s,m+1,y,root->r); 85 root->data -= s; 86 } 87 } 88 89 int query(int ml,int mr,int z,int y,struct N *root) 90 { 91 int m = (z+y)/2; 92 93 if(ml == z && mr == y) 94 return root->data; 95 96 if(mr <= m) 97 { 98 return query(ml,mr,z,m,root->l); 99 } 100 else if(m+1 <= ml) 101 { 102 return query(ml,mr,m+1,y,root->r); 103 } 104 else 105 { 106 return ( query(ml,m,z,m,root->l) + query(m+1,mr,m+1,y,root->r) ); 107 } 108 } 109 110 int main() 111 { 112 int T; 113 int icase = 0; 114 int n,i; 115 char order[20]; 116 scanf("%d",&T); 117 while(T--) 118 { 119 scanf("%d",&n); 120 for(i = 1;i <= n; i++) 121 { 122 scanf("%d",&st[i]); 123 } 124 struct N *root = creat(); 125 126 root->z = 1; 127 root->y = n; 128 129 change(1,n,root); 130 131 printf("Case %d:\n",++icase); 132 133 while(scanf("%s",order) != EOF) 134 { 135 if(order[0] == 'E') 136 break; 137 else if(order[0] == 'A') 138 { 139 int site,s; 140 scanf("%d %d",&site,&s); 141 add(site,s,1,n,root); 142 } 143 else if(order[0] == 'S') 144 { 145 int site,s; 146 scanf("%d %d",&site,&s); 147 sub(site,s,1,n,root); 148 } 149 else if(order[0] == 'Q') 150 { 151 int l,r; 152 scanf("%d %d",&l,&r); 153 int sum = query(l,r,1,n,root); 154 printf("%d\n",sum); 155 } 156 } 157 158 } 159 return 0; 160 }
1 #include <cstdio>//用数组模拟的线段树 跑了370+ 玛德 说好的0ms呢 2 #include <algorithm>//在大白书 点修改 上看的 就是在不停的传递 树的节点编号node 3 #include <iostream>//当前节点的左子节点编号为2*node 右子节点为2*node+1； 4 #include <cstdlib> 5 #include <queue> 6 #include <cmath> 7 #include <cstring> 8 9 using namespace std; 10 11 int st[100010]; 12 int a[50001]; 13 14 int change(int node,int l,int r) 15 { 16 int m = (l+r)/2; 17 if(l == r) 18 { 19 st[node] = a[l]; 20 return st[node]; 21 } 22 st[node] = change(node+node,l,m) + change(node+node+1,m+1,r); 23 return st[node]; 24 } 25 26 void add(int site,int s,int node,int l,int r) 27 { 28 int m = (l+r)/2; 29 30 if(l == r && r == site) 31 { 32 st[node] += s; 33 return ; 34 } 35 if(site <= m) 36 { 37 add(site,s,node+node,l,m); 38 st[node] += s; 39 return ; 40 } 41 if(m < site) 42 { 43 add(site,s,node+node+1,m+1,r); 44 st[node] += s; 45 return ; 46 } 47 } 48 49 void sub(int site,int s,int node,int l,int r) 50 { 51 int m = (l+r)/2; 52 53 if(l == r && r == site) 54 { 55 st[node] -= s; 56 return ; 57 } 58 if(site <= m) 59 { 60 sub(site,s,node+node,l,m); 61 st[node] -= s; 62 return ; 63 } 64 if(m < site) 65 { 66 sub(site,s,node+node+1,m+1,r); 67 st[node] -= s; 68 return ; 69 } 70 } 71 72 int query(int ml,int mr,int node,int l,int r) 73 { 74 if(ml == l && mr == r) 75 { 76 return st[node]; 77 } 78 int m = (l+r)/2; 79 80 if(mr <= m) 81 { 82 return query(ml,mr,node+node,l,m); 83 } 84 if(m < ml) 85 { 86 return query(ml,mr,node+node+1,m+1,r); 87 } 88 return (query(ml,m,node+node,l,m) + query(m+1,mr,node+node+1,m+1,r)); 89 } 90 91 int main() 92 { 93 int T,icase = 0; 94 int n,i; 95 char order[6]; 96 97 scanf("%d",&T); 98 99 100 while(T--) 101 { 102 scanf("%d",&n); 103 for(i = 1;i <= n; i++) 104 scanf("%d",&a[i]); 105 change(1,1,n); 106 printf("Case %d:\n",++icase); 107 while(scanf("%s",order) != EOF) 108 { 109 if(order[0] == 'A') 110 { 111 int site,s; 112 scanf("%d %d",&site,&s); 113 add(site,s,1,1,n); 114 } 115 else if(order[0] == 'S') 116 { 117 int site,s; 118 scanf("%d %d",&site,&s); 119 sub(site,s,1,1,n); 120 } 121 else if(order[0] == 'Q') 122 { 123 int l,r; 124 scanf("%d %d",&l,&r); 125 printf("%d\n",query(l,r,1,1,n)); 126 } 127 else if(order[0] == 'E') 128 break; 129 } 130 131 } 132 return 0; 133 }