首页 > 代码库 > hdu1166 单点更新

hdu1166 单点更新

  第一道线段树,对着学长给的板子敲,嘿嘿,纪念一下~~~

  代码:

 

 1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <string.h> 5 #include <cmath> 6 #include <cstdlib> 7 #include <algorithm> 8  9 using namespace std;10 11 const int maxn = 50000 + 10;12 int a[maxn];13 14 struct node15 {16     int left, right, sum;17 } b[maxn*4];18 19 void build(int left, int right, int i)20 {21     b[i].left = left;22     b[i].right = right;23     int mid = (left + right)/2;24     if(left == right) {25         b[i].sum = a[left];26         return ;27     }28     build(left, mid, 2*i);29     build(mid+1, right, 2*i+1);30     b[i].sum = b[2*i].sum + b[2*i+1].sum;31 }32 33 void Add(int id, int num, int i)34 {35     if(b[i].left == b[i].right) {36         b[i].sum += num;37         return ;38     }39     else {40         b[i].sum += num;41         if(id <= b[2*i].right) Add(id, num, 2*i);42         else Add(id, num, 2*i+1);43     }44 }45 46 int Query(int left, int right, int i)47 {48     int mid;49     if(left == b[i].left && right == b[i].right) {50         return b[i].sum;51     }52     mid = (b[i].left + b[i].right)/2;53     if(right <= mid) return Query(left, right, 2*i);54     else if(left > mid) return Query(left, right, 2*i+1);55     else return Query(left, mid, 2*i) + Query(mid+1, right, 2*i+1);56 }57 58 int main()59 {60     //freopen("test.in", "r", stdin);61     char s[10];62     int T, N, x, y;63     scanf("%d", &T);64     int t = T;65     while(T--)66     {67         printf("Case %d:\n", t-T);68         scanf("%d", &N);69         for(int i = 1; i <= N; i++)70             scanf("%d", &a[i]);71         build(1, N, 1);72         while(1) {73             scanf("%s", s);74             if(s[0] == E) break;75             scanf("%d%d", &x, &y);76             if(s[0] == Q) printf("%d\n", Query(x, y, 1));77             else if(s[0] == A) Add(x, y, 1);78             else Add(x, -y, 1);79         }80     }81     return 0;82 }
View Code