首页 > 代码库 > 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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。