首页 > > 程序设计 > C/C++ >

线段树题解（3题）

2018-06-17 21:48:58来源：未知阅读 ()

A - 敌兵布阵

C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是要监视这些工兵营地的活动情况。由于采取了某种先进的监测手段，所以每个工兵营地的人数C国都掌握的一清二楚,每个工兵营地的人数都有可能发生变动，可能增加或减少若干人手,但这些都逃不过C国的监视。
中央情报局要研究敌人究竟演习什么战术,所以Tidy要随时向Derek汇报某一段连续的工兵营地一共有多少人,例如Derek问:“Tidy,马上汇报第3个营地到第10个营地共有多少人!”Tidy就要马上开始计算这一段的总人数并汇报。但敌兵营地的人数经常变动，而Derek每次询问的段都不一样，所以Tidy不得不每次都一个一个营地的去数，很快就精疲力尽了，Derek对Tidy的计算速度越来越不满:"你个死肥仔，算得这么慢，我炒你鱿鱼!”Tidy想：“你自己来算算看，这可真是一项累人的工作!我恨不得你炒我鱿鱼呢!”无奈之下，Tidy只好打电话向计算机专家Windbreaker求救,Windbreaker说：“死肥仔，叫你平时做多点acm题和看多点算法书，现在尝到苦果了吧!”Tidy说："我知错了。。。"但Windbreaker已经挂掉电话了。Tidy很苦恼，这么算他真的会崩溃的，聪明的读者，你能写个程序帮他完成这项工作吗？不过如果你的程序效率不够高的话，Tidy还是会受到Derek的责骂的.

Input第一行一个整数T，表示有T组数据。
每组数据第一行一个正整数N（N<=50000）,表示敌人有N个工兵营地，接下来有N个正整数,第i个正整数ai代表第i个工兵营地里开始时有ai个人（1<=ai<=50）。
接下来每行有一条命令，命令有4种形式：
(1) Add i j,i和j为正整数,表示第i个营地增加j个人（j不超过30）
(2)Sub i j ,i和j为正整数,表示第i个营地减少j个人（j不超过30）;
(3)Query i j ,i和j为正整数,i<=j，表示询问第i到第j个营地的总人数;
(4)End 表示结束，这条命令在每组数据最后出现;
每组数据最多有40000条命令
Output对第i组数据,首先输出“Case i:”和回车,
对于每个Query询问，输出一个整数并回车,表示询问的段中的总人数,这个数保持在int以内。
Sample Input

1
10
1 2 3 4 5 6 7 8 9 10
Query 1 3
Add 3 6
Query 2 7
Sub 10 2
Add 6 3
Query 3 10
End

Sample Output

Case 1:
6
33
59

B - I Hate It

很多学校流行一种比较的习惯。老师们很喜欢询问，从某某到某某当中，分数最高的是多少。
这让很多学生很反感。

不管你喜不喜欢，现在需要你做的是，就是按照老师的要求，写一个程序，模拟老师的询问。当然，老师有时候需要更新某位同学的成绩。

Input本题目包含多组测试，请处理到文件结束。
在每个测试的第一行，有两个正整数 N 和 M ( 0<N<=200000,0<M<5000 )，分别代表学生的数目和操作的数目。
学生ID编号分别从1编到N。
第二行包含N个整数，代表这N个学生的初始成绩，其中第i个数代表ID为i的学生的成绩。
接下来有M行。每一行有一个字符 C (只取'Q'或'U') ，和两个正整数A，B。
当C为'Q'的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。
当C为'U'的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。
Output对于每一次询问操作，在一行里面输出最高成绩。Sample Input

Sample Output

C - A Simple Problem with Integers

You have N integers, A₁, A₂, ... , A_N. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A₁, A₂, ... , A_N. -1000000000 ≤ A_i ≤ 1000000000.
Each of the next Q lines represents an operation.
"C a b c" means adding c to each of A_a, A_a₊₁, ... , A_b. -10000 ≤ c ≤ 10000.
"Q a b" means querying the sum of A_a, A_a₊₁, ... , A_b.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

4
55
9
15



这3题都是线段树的模板题了，A题是点修改的求和问题，B题则是求一个区间中的最大值，C题是区间修改的求和问题。

为啥这些题要用线段树这种数据结构来存储呢？当然是为了减少时间复杂度，从A题可以看出N的最大值为50000，而执行的操作也有40000之多，如果用一般的数组来存储数据，再进行区间求和和点修改。。。
即：1. 对于简单的区间求和，我们有两种做法，1是直接将区间中的数相加，那么所需的时间复杂度为O(n),而操作次数有40000次，N的最大值为50000，那么最后肯定会超时，第二种方法则是用数组存之前所有树的和，那么每次查询
操作只需要O(1)，这是不会超时的。
2. 对于定点修改，

很明显两种方法都会超时。而线段树的时间复杂度只有log2(R-L+1)。

线段树用的存储结构是二叉树，但每一个节点中存的东西都是你所要求的东西。

对于线段树来说，最先要实现的就是Build（）函数，即建树。

接着便是PushUp（）函数，PushUp（）函数的作用是修改你所修改区间的父区间的值，而PushDown（）恰恰相反，PushDown（）是修改你所修改区间的子区间的值，但实现PushDown（）

的作用需要一个懒惰标记，即但你递归到被修改区间的子区间时，则会将标记下推，同时修改子区间的值。

然后便是Update（）函数，即修改函数。最后用Query（）函数得出答案即可。

由于都是模板题，就直接贴码了。

如果对于线段树没有什么了解的可以去这里了解一下：http://blog.csdn.net/zearot/article/details/48299459

A题：

 1 #include <stdio.h>
 2 
 3 #define max 50002
 4 
 5 int p[max], n;
 6 int m[max<<2];
 7 
 8 void PushUp(int rt) {
 9     m[rt] = m[rt << 1] + m[rt << 1 | 1];
10 }
11 
12 void Build(int l, int r, int rt) {
13     if (l == r) {
14         m[rt] = p[l];
15         return;
16     }
17     int j = (l + r) >> 1;
18     Build(l, j, rt << 1);
19     Build(j + 1, r, rt << 1 | 1);
20     PushUp(rt);
21 }
22 
23 void Updata(int L, int C, int l, int r, int rt) {
24     if (l == r) {
25         m[rt] += C;
26         return;
27     }
28     int j = (l + r) >> 1;
29     if (L <= j)Updata(L, C, l, j, rt << 1);
30     else Updata(L, C, j + 1, r, rt << 1 | 1);
31     PushUp(rt);
32 }
33 
34 int Query(int L, int R, int l, int r, int rt) {
35     if (L <= l&&r <= R) {
36         return m[rt];
37     }
38     int j = (l + r) >> 1;
39     int ans = 0;
40     if (L <= j)ans += Query(L, R, l, j, rt << 1);
41     if (R > j)ans += Query(L, R, j + 1, r, rt << 1 | 1);
42     return ans;
43 }
44 
45 int main()
46 {
47     int t;
48     scanf("%d", &t);
49     int count = 1;
50     while (t--) {
51         scanf("%d", &n);
52         for (int i = 1; i <= n; i++) {
53             scanf("%d", &p[i]);
54         }
55         char k[10];
56         printf("Case %d:\n", count++);
57         Build(1, n, 1);
58         while (1) {
59             scanf("%s",&k);
60             if (k[0] == 'Q') {
61                 int a, b;
62                 scanf("%d%d", &a, &b);
63                 int ans = Query(a, b, 1, n, 1);
64                 printf("%d\n", ans);
65             }
66             else if (k[0] == 'A') {
67                 int a, b;
68                 scanf("%d%d", &a, &b);
69                 Updata(a, b, 1, n, 1);
70             }
71             else if (k[0] == 'S') {
72                 int a, b;
73                 scanf("%d%d", &a, &b);
74                 Updata(a, -b, 1, n, 1);
75             }
76             else {
77                 break;
78             }
79         }
80     }
81     return 0;
82 }

View Code

B题：

 1 #include <stdio.h>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 #define Max 200002
 6 
 7 int p[Max], n, m, ans;
 8 int sum[Max << 2];
 9 
10 void PushUp(int rt) {
11     sum[rt] = max(sum[rt << 1], sum[rt << 1 | 1]);
12 }
13 
14 void Build(int l, int r, int rt) {
15     if (l == r) {
16         sum[rt] = p[l];
17         return;
18     }
19     int j = (l + r) >> 1;
20     Build(l, j, rt << 1);
21     Build(j + 1, r, rt << 1 | 1);
22     PushUp(rt);
23 }
24 
25 void Updata(int L, int C, int l, int r, int rt) {
26     if (l == r) {
27         sum[rt] = C;
28         return;
29     }
30     int j = (l + r) >> 1;
31     if (L <= j)Updata(L, C, l, j, rt << 1);
32     else Updata(L, C, j + 1, r, rt << 1 | 1);
33     PushUp(rt);
34 }
35 
36 void Query(int L, int R, int l, int r, int rt) {
37     if (L <= l&&r <= R) {
38         ans = max(ans, sum[rt]);
39         return;
40     }
41     int j = (l + r) >> 1;
42     if (L <= j) Query(L, R, l, j, rt << 1);
43     if (R > j)Query(L, R, j + 1, r, rt << 1 | 1);
44 }
45 
46 int main()
47 {
48     while (scanf("%d%d", &n, &m) != EOF) {
49         for (int i = 1; i <= n; i++) {
50             scanf("%d", &p[i]);
51         }
52         Build(1, n, 1);
53         char q[5];
54         int a, b;
55         for (int i = 1; i <= m; i++) {
56             scanf("%s", q);
57             scanf("%d%d",&a,&b);
58             if (q[0] == 'Q') {
59                 ans = 0;
60                 Query(a, b, 1, n, 1);
61                 printf("%d\n", ans);
62             }
63             else if (q[0] == 'U') {
64                 p[a] = b;
65                 Updata(a, b, 1, n, 1);
66             }
67         }
68     }
69     return 0;
70 }

View Code

C题：

 1 #include <stdio.h>
 2 #include <string.h>
 3 
 4 #define Maxn 100002
 5 
 6 long long Sum[Maxn << 2], Add[Maxn << 2];
 7 long long A[Maxn], n, m;
 8 
 9 void PushUp(int rt) {
10     Sum[rt] = Sum[rt << 1] + Sum[rt << 1 | 1];
11 }
12 
13 void PushDown(int rt,int ln,int rn) {
14     if (Add[rt]) {
15         Add[rt << 1] += Add[rt];
16         Add[rt << 1 | 1] += Add[rt];
17         Sum[rt << 1] += Add[rt] * ln;
18         Sum[rt << 1 | 1] += Add[rt] * rn;
19         Add[rt] = 0;
20     }
21 }
22 
23 void Build(int l, int r, int rt) {
24     if (l == r) {
25         Sum[rt] = A[l];
26         return;
27     }
28     int j = (l + r) >> 1;
29     Build(l, j, rt << 1);
30     Build(j + 1, r, rt << 1 | 1);
31     PushUp(rt);
32 }
33 
34 /*void Updata(int R, int C, int l, int r, int rt) {
35     if (l == r) {
36         Sum[rt] += C;
37         return;
38     }
39     int j = (l + r) >> 1;
40     PushDown(rt, j - l + 1, r - m);
41     if (R <= j)Updata(R, C, l, j, rt << 1);
42     else Updata(R, C, j + 1, r, rt << 1 | 1);
43     PushUp(rt);
44 }*/
45 
46 void Updata(int L, int R, int C, int l, int r, int rt) {
47     if (L <= l&&r <= R) {
48         Sum[rt] += (r - l + 1)*C;
49         Add[rt] += C;
50         return;
51     }
52     int j = (l + r) >> 1;
53     PushDown(rt, j - l + 1, r - j);
54     if (L <= j)Updata(L, R, C, l, j, rt<<1);
55     if (R > j)Updata(L, R, C, j + 1, r, rt << 1 | 1);
56     PushUp(rt);
57 }
58 
59 long long Query(int L, int R, int l, int r, int rt) {
60     if (L <= l&&r <= R) {
61         return Sum[rt];
62     }
63     int j = (l + r) >> 1;
64     PushDown(rt, j - l + 1, r - j);
65     long long ans = 0;
66     if (L <= j)ans += Query(L, R, l, j, rt << 1);
67     if (R > j)ans += Query(L, R, j + 1, r, rt << 1 | 1);
68     return ans;
69 }
70 
71 int main()
72 {
73     while (scanf("%lld%lld", &n, &m) != EOF) {
74         for (int i = 1; i <= n; i++) {
75             scanf("%lld", &A[i]);
76         }
77         memset(Add, 0, sizeof(Add));
78         Build(1, n, 1);
79         char p[5];
80         for (int i = 1; i <= m; i++) {
81             scanf("%s", p);
82             if (p[0] == 'Q') {
83                 int a, b;
84                 scanf("%d%d", &a, &b);
85                 printf("%I64d\n", Query(a, b, 1, n, 1));
86             }
87             else {
88                 int a, b, c;
89                 scanf("%d%d%d", &a, &b, &c);
90                 Updata(a, b, c, 1, n, 1);
91             }
92         }
93     }
94     return 0;
95 }