題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=1166 人生第一道線段樹基礎題，考察的是單點更新，今天剛剛學習了一下線段樹，膜拜一下notonlysuccess大神，在他的博客里面，線段樹的幾種操作的實現方法我弄明白了，不過寫起來還是糾結，看來還應該多多練習，怎么說也得各種做，慢慢刷，刷到我很NB為止吧…… 線段樹的講解很多大神已經相當明白了，我也就不班門弄斧了，代碼也幾乎和notonlysuccess大神一樣的，從此也以此做為我的基礎模板。
  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
|