题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1166 人生第一道线段树基础题,考察的是单点更新,今天刚刚学习了一下线段树,膜拜一下notonlysuccess大神,在他的博客里面,线段树的几种操作的实现方法我弄明白了,不过写起来还是纠结,看来还应该多多练习,怎么说也得各种做,慢慢刷,刷到我很NB为止吧…… 线段树的讲解很多大神已经相当明白了,我也就不班门弄斧了,代码也几乎和notonlysuccess大神一样的,从此也以此做为我的基础模板。
![](/Images/OutliningIndicators/ContractedBlock.gif) view code 1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cmath> 6 #include <algorithm> 7 using namespace std; 8 const int maxn = 55555; 9 int sum[maxn << 2]; 10 void PushUp(int rt) 11 { 12 sum[rt] = sum[rt << 1] + sum[rt << 1 | 1]; 13 } 14 void build(int l, int r, int rt) 15 { 16 if (l == r) 17 { 18 scanf("%d", &sum[rt]); 19 return; 20 } 21 int m = (l + r) >> 1; 22 build(l, m, rt << 1); 23 build(m + 1, r, rt << 1 | 1); 24 PushUp(rt); 25 } 26 void update(int p, int add, int l, int r, int rt) 27 { 28 if (l == r) 29 { 30 sum[rt] += add; 31 return; 32 } 33 int m = (l + r) >> 1; 34 if (p <= m) update(p, add, l, m, rt << 1); 35 else update(p, add, m + 1, r, rt << 1 | 1); 36 PushUp(rt); 37 } 38 int query(int ll, int rr, int l, int r, int rt) 39 { 40 if (ll <= l && rr >= r) return sum[rt]; 41 int m = (l + r) >> 1; 42 int ret = 0; 43 if (ll <= m) ret += query(ll, rr, l, m, rt << 1); 44 if (rr > m) ret += query(ll, rr, m + 1, r, rt << 1 | 1); 45 return ret; 46 } 47 int main() 48 { 49 int t, c; 50 char d[10]; 51 scanf("%d", &t); 52 for (c = 1; c <= t; c++) 53 { 54 printf("Case %d:\n", c); 55 int n; scanf("%d", &n); 56 build(1, n, 1); 57 while (scanf("%s", d) != EOF) 58 { 59 if (d[0] == 'E') break; 60 int x, y; scanf("%d%d", &x, &y); 61 if (d[0] == 'Q') 62 { 63 int ans = query(x, y, 1, n, 1); 64 printf("%d\n", ans); 65 } 66 if (d[0] == 'S') update(x, -y, 1, n, 1); 67 if (d[0] == 'A') update(x, y, 1, n, 1); 68 } 69 } 70 return 0; 71
|