【线段树基础】NKOJ 1321 数列操作

时间限制 : 10000 MS 空间限制 : 165536 KB

问题描述

假设有一列数{Ai}(1≤i≤n)，支持如下两种操作：
将Ak的值加D。（k, D是输入的数）
输出As+As+1+…+At。（s, t都是输入的数，S≤T）

输入格式

第一行一个整数n，
第二行为n个整数，表示{Ai}的初始值≤10000。
第三行为一个整数m，表示操作数
下接m行，每行描述一个操作，有如下两种情况：
ADD k d (表示将Ak加d，1<=k<=n，d为数,d的绝对值不超过10000)
SUM s t （表示输出As+…+At）

输出格式

对于每一个SUM提问，输出结果

样例输入 1

5
1 2 3 2 4
5
SUM 1 2
SUM 1 5
ADD 1 2
SUM 1 2
SUM 1 5

样例输出 1

3
12
5
14

样例输入 2

10
44 37 20 29 13 8 32 14 46 29
8
ADD 5 3
SUM 1 8
SUM 4 6
ADD 3 18
SUM 2 5
ADD 4 15
SUM 1 7
SUM 5 10

样例输出 2

200
53
120
219
145

提示

M,N<=100000

【提示】

线段树板题

【参考代码】

 1 #include<cstdio>
 2 #define maxn 100003
 3 int n, m;
 4 int A[maxn];
 5 char op[3];
 6 struct node {
 7     int a, b, v;
 8 }Tree[maxn << 2];
 9 namespace Ironclad_Programming {
10     #define R register int
11     #define For(i, s, n) for (R i = s; i <= n; ++ i)
12     namespace ini {
13         void MakeTree(int p, int x, int y) {
14             Tree[p].a = x;
15             Tree[p].b = y;
16             if (x < y) {
17                 MakeTree(p * 2, x, ((x + y) >> 1));
18                 MakeTree(p * 2 + 1, ((x + y) >> 1) + 1, y);
19                 Tree[p].v = Tree[p * 2].v + Tree[p * 2 + 1].v;
20             } else Tree[p].v = A[x];
21         }
22         void executive() {
23             scanf("%d", &n);
24             For (i, 1, n)scanf("%d", &A[i]);
25             MakeTree(1, 1, n);
26         }
27     }
28     namespace solve {
29         void Add(int p, int k, int d) {
30             Tree[p].v += d;
31             if (Tree[p].a == Tree[p].b)return;
32             if (Tree[p * 2].a <= k && Tree[p * 2].b >= k)Add(p * 2, k, d);
33             if (Tree[p * 2 + 1].a <= k && Tree[p * 2 + 1].b >= k)Add(p * 2 + 1, k, d);
34         }
35         int GetSum(int p, int s, int t) {
36             if (t < Tree[p].a || s > Tree[p].b)return 0;
37             if (s <= Tree[p].a && Tree[p].b <= t)return Tree[p].v;
38             else {
39                 int Total = 0;
40                 Total += GetSum(p * 2, s, t);
41                 Total += GetSum(p * 2 + 1, s, t);
42                 return Total;
43             }
44         }
45         void executive() {
46             scanf("%d", &m);
47             For (i, 1, m) {
48                 scanf("%s", op);
49                 if (op[0] == 'A') {
50                     int k, d;
51                     scanf("%d%d", &k, &d);
52                     Add(1, k, d);
53                 } else {
54                     int s, t;
55                     scanf("%d%d", &s, &t);
56                     printf("%d
", GetSum(1, s, t));
57                 }
58             }
59         }
60     }
61     void Main() {
62         ini::executive();
63         solve::executive();
64     }
65     #undef R
66     #undef For
67 }
68 int main() {
69     Ironclad_Programming::Main();
70     return 0;
71 }