树状数组

101 阅读 0 评论 67 点赞

我是靠谱客的博主无私招牌，这篇文章主要介绍树状数组，现在分享给大家，希望可以做个参考。

树状数组

树状数组是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和，但是每次只能修改一个元素的值；经过简单修改可以在log(n)的复杂度下进行范围修改，但是这时只能查询其中一个元素的值(如果加入多个辅助数组则可以实现区间修改与区间查询)。

树状数组与线段树的区别：

1.线段数和树状数组可以修改，而前缀和不能修改。
2.树状数组空间复杂度较低。

树状数组的原理：

假设数组a[n]，要求它任意区间的和，并且支持修改任意数的值，树状数组利用二进制来实现该功能。

知道这一点，我们假设a[8]={1,2,3,4,5,6,7,8},下面看一下它实现的过程。

在说这个过程代码实现之前说一下lowerbit的作用及原理：

1.lowerbit(x)可以讲x对应的二进制数，从右边数第一个1不变，其他全变成0,例如x=1010100，那么lowerbit(x)=0000100。

2.lowerbit(x)的原理实际上就是执行 x&(-x) 的过程，例如：x=10101000，那么-x=010101000(-x的求出过程，先将符号位的1变成0再将其他位求反，最后再加上1)，则 x&(-x) = 00001000

下面图中所给思想的实现过程：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void init(int n)
{
for (int i = 1; i <= n; ++i)
{
scanf("%d", &a[i]);
maxVal[i] = a[i];//以后的a[i]还要修改呢//
for (int j = 1; j < lowbit(i); j <<= 1)
// 与所有涉及到的子区间段最大值比较
{
maxVal[i] = max(maxVal[i], maxVal[i - j]);
}
}
}

接下来我们看修改值函数的实现：

复制代码

void update(int x, int val, int n) // 单单改变父亲结点是不够的，因为无法确定这段区间中的最大值来自哪里，
{
// 所以还需要与子区间进行比较确定最大值
a[x] = val;
for (int i = x; i <= n; i += lowbit(i))
{
maxVal[i] = a[i];
for (int j = 1; j < lowbit(i); j <<= 1)
{
maxVal[i] = max(maxVal[i], maxVal[i - j]);
}
}
}
最后看寻找最大值的函数：

int getMax(int l, int r)
{
int ret = a[r];
while (l != r)
{
for (r -= 1; r - lowbit(r) >= l; r -= lowbit(r)) // 1.判断是区间是否在查询范围内
{
ret = max(ret, maxVal[r]);
}
ret = max(ret, a[r]); // 2.如果不在查询范围内，则只能将第r个数加入判断
}
return ret;
}
下面举个例题说明一下；

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
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5
Sample Output
5
6
5
9
Hint
Huge input,the C function scanf() will work better than cin

#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN = 2e5 + 111;
int maxVal[MAXN], a[MAXN];
int lowbit(int x)
{
return x & -x;
}
void init(int n)
{
for (int i = 1; i <= n; ++i)
{
scanf("%d", &a[i]);
maxVal[i] = a[i];
for (int j = 1; j < lowbit(i); j <<= 1)
// 与所有涉及到的子区间段最大值比较
{
maxVal[i] = max(maxVal[i], maxVal[i - j]);
}
}
}
int getMax(int l, int r)
{
int ret = a[r];
while (l != r)
{
for (r -= 1; r - lowbit(r) >= l; r -= lowbit(r)) // 1.判断是区间是否在查询范围内
{
ret = max(ret, maxVal[r]);
}
ret = max(ret, a[r]); // 2.如果不在查询范围内，则只能将第r个数加入判断
}
return ret;
}
void update(int x, int val, int n) // 单单改变父亲结点是不够的，因为无法确定这段区间中的最大值来自哪里，
{
// 所以还需要与子区间进行比较确定最大值
a[x] = val;
for (int i = x; i <= n; i += lowbit(i))
{
maxVal[i] = a[i];
for (int j = 1; j < lowbit(i); j <<= 1)
{
maxVal[i] = max(maxVal[i], maxVal[i - j]);
}
}
}
int main()
{
int n, m, a, b;
while (~scanf("%d%d", &n, &m))
{
init(n);
char op[2];
for (int i = 0; i < m; ++i)
{
scanf("%s%d%d", op, &a, &b);
if (op[0] == 'Q') printf("%dn", getMax(a, b));
else update(a, b, n);
}
}
return 0;
}

练习地址：https://cn.vjudge.net/contest/179845
愿你一生清澈明朗，做您愿做之事，爱你愿爱之人!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
复制代码void update(int x, int val, int n) // 单单改变父亲结点是不够的，因为无法确定这段区间中的最大值来自哪里，
{
// 所以还需要与子区间进行比较确定最大值
a[x] = val;
for (int i = x; i <= n; i += lowbit(i))
{
maxVal[i] = a[i];
for (int j = 1; j < lowbit(i); j <<= 1)
{
maxVal[i] = max(maxVal[i], maxVal[i - j]);
}
}
}
void update(int x, int val, int n) // 单单改变父亲结点是不够的，因为无法确定这段区间中的最大值来自哪里，
{
// 所以还需要与子区间进行比较确定最大值
a[x] = val;
for (int i = x; i <= n; i += lowbit(i))
{
maxVal[i] = a[i];
for (int j = 1; j < lowbit(i); j <<= 1)
{
maxVal[i] = max(maxVal[i], maxVal[i - j]);
}
}
}
最后看寻找最大值的函数：
复制代码
复制代码int getMax(int l, int r)
{
int ret = a[r];
while (l != r)
{
for (r -= 1; r - lowbit(r) >= l; r -= lowbit(r)) // 1.判断是区间是否在查询范围内
{
ret = max(ret, maxVal[r]);
}
ret = max(ret, a[r]); // 2.如果不在查询范围内，则只能将第r个数加入判断
}
return ret;
}
下面举个例题说明一下；



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
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5
Sample Output
5
6
5
9
Hint
Huge input,the C function scanf() will work better than cin





#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN = 2e5 + 111;
int maxVal[MAXN], a[MAXN];
int lowbit(int x)
{
return x & -x;
}
void init(int n)
{
for (int i = 1; i <= n; ++i)
{
scanf("%d", &a[i]);
maxVal[i] = a[i];
for (int j = 1; j < lowbit(i); j <<= 1)
// 与所有涉及到的子区间段最大值比较
{
maxVal[i] = max(maxVal[i], maxVal[i - j]);
}
}
}
int getMax(int l, int r)
{
int ret = a[r];
while (l != r)
{
for (r -= 1; r - lowbit(r) >= l; r -= lowbit(r)) // 1.判断是区间是否在查询范围内
{
ret = max(ret, maxVal[r]);
}
ret = max(ret, a[r]); // 2.如果不在查询范围内，则只能将第r个数加入判断
}
return ret;
}
void update(int x, int val, int n) // 单单改变父亲结点是不够的，因为无法确定这段区间中的最大值来自哪里，
{
// 所以还需要与子区间进行比较确定最大值
a[x] = val;
for (int i = x; i <= n; i += lowbit(i))
{
maxVal[i] = a[i];
for (int j = 1; j < lowbit(i); j <<= 1)
{
maxVal[i] = max(maxVal[i], maxVal[i - j]);
}
}
}
int main()
{
int n, m, a, b;
while (~scanf("%d%d", &n, &m))
{
init(n);
char op[2];
for (int i = 0; i < m; ++i)
{
scanf("%s%d%d", op, &a, &b);
if (op[0] == 'Q') printf("%dn", getMax(a, b));
else update(a, b, n);
}
}
return 0;
}



练习地址：https://cn.vjudge.net/contest/179845
愿你一生清澈明朗，做您愿做之事，爱你愿爱之人!




复制代码int getMax(int l, int r)
{
int ret = a[r];
while (l != r)
{
for (r -= 1; r - lowbit(r) >= l; r -= lowbit(r)) // 1.判断是区间是否在查询范围内
{
ret = max(ret, maxVal[r]);
}
ret = max(ret, a[r]); // 2.如果不在查询范围内，则只能将第r个数加入判断
}
return ret;
}
int getMax(int l, int r)
{
int ret = a[r];
while (l != r)
{
for (r -= 1; r - lowbit(r) >= l; r -= lowbit(r)) // 1.判断是区间是否在查询范围内
{
ret = max(ret, maxVal[r]);
}
ret = max(ret, a[r]); // 2.如果不在查询范围内，则只能将第r个数加入判断
}
return ret;
}
下面举个例题说明一下；
复制代码
复制代码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
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5
Sample Output
5
6
5
9
Hint
Huge input,the C function scanf() will work better than cin

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
5 6
1 2 3 4 5
Q 1 5
U 3 6
Q 3 4
Q 4 5
U 2 9
Q 1 5
Sample Output
5
6
5
9
Hint
Huge input,the C function scanf() will work better than cin
复制代码


#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN = 2e5 + 111;
int maxVal[MAXN], a[MAXN];
int lowbit(int x)
{
return x & -x;
}
void init(int n)
{
for (int i = 1; i <= n; ++i)
{
scanf("%d", &a[i]);
maxVal[i] = a[i];
for (int j = 1; j < lowbit(i); j <<= 1)
// 与所有涉及到的子区间段最大值比较
{
maxVal[i] = max(maxVal[i], maxVal[i - j]);
}
}
}
int getMax(int l, int r)
{
int ret = a[r];
while (l != r)
{
for (r -= 1; r - lowbit(r) >= l; r -= lowbit(r)) // 1.判断是区间是否在查询范围内
{
ret = max(ret, maxVal[r]);
}
ret = max(ret, a[r]); // 2.如果不在查询范围内，则只能将第r个数加入判断
}
return ret;
}
void update(int x, int val, int n) // 单单改变父亲结点是不够的，因为无法确定这段区间中的最大值来自哪里，
{
// 所以还需要与子区间进行比较确定最大值
a[x] = val;
for (int i = x; i <= n; i += lowbit(i))
{
maxVal[i] = a[i];
for (int j = 1; j < lowbit(i); j <<= 1)
{
maxVal[i] = max(maxVal[i], maxVal[i - j]);
}
}
}
int main()
{
int n, m, a, b;
while (~scanf("%d%d", &n, &m))
{
init(n);
char op[2];
for (int i = 0; i < m; ++i)
{
scanf("%s%d%d", op, &a, &b);
if (op[0] == 'Q') printf("%dn", getMax(a, b));
else update(a, b, n);
}
}
return 0;
}



练习地址：https://cn.vjudge.net/contest/179845
愿你一生清澈明朗，做您愿做之事，爱你愿爱之人!






复制代码




复制代码

复制代码#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN = 2e5 + 111;
int maxVal[MAXN], a[MAXN];
int lowbit(int x)
{
return x & -x;
}
void init(int n)
{
for (int i = 1; i <= n; ++i)
{
scanf("%d", &a[i]);
maxVal[i] = a[i];
for (int j = 1; j < lowbit(i); j <<= 1)
// 与所有涉及到的子区间段最大值比较
{
maxVal[i] = max(maxVal[i], maxVal[i - j]);
}
}
}
int getMax(int l, int r)
{
int ret = a[r];
while (l != r)
{
for (r -= 1; r - lowbit(r) >= l; r -= lowbit(r)) // 1.判断是区间是否在查询范围内
{
ret = max(ret, maxVal[r]);
}
ret = max(ret, a[r]); // 2.如果不在查询范围内，则只能将第r个数加入判断
}
return ret;
}
void update(int x, int val, int n) // 单单改变父亲结点是不够的，因为无法确定这段区间中的最大值来自哪里，
{
// 所以还需要与子区间进行比较确定最大值
a[x] = val;
for (int i = x; i <= n; i += lowbit(i))
{
maxVal[i] = a[i];
for (int j = 1; j < lowbit(i); j <<= 1)
{
maxVal[i] = max(maxVal[i], maxVal[i - j]);
}
}
}
int main()
{
int n, m, a, b;
while (~scanf("%d%d", &n, &m))
{
init(n);
char op[2];
for (int i = 0; i < m; ++i)
{
scanf("%s%d%d", op, &a, &b);
if (op[0] == 'Q') printf("%dn", getMax(a, b));
else update(a, b, n);
}
}
return 0;
}
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN = 2e5 + 111;
int maxVal[MAXN], a[MAXN];
int lowbit(int x)
{
return x & -x;
}
void init(int n)
{
for (int i = 1; i <= n; ++i)
{
scanf("%d", &a[i]);
maxVal[i] = a[i];
for (int j = 1; j < lowbit(i); j <<= 1)
// 与所有涉及到的子区间段最大值比较
{
maxVal[i] = max(maxVal[i], maxVal[i - j]);
}
}
}
int getMax(int l, int r)
{
int ret = a[r];
while (l != r)
{
for (r -= 1; r - lowbit(r) >= l; r -= lowbit(r)) // 1.判断是区间是否在查询范围内
{
ret = max(ret, maxVal[r]);
}
ret = max(ret, a[r]); // 2.如果不在查询范围内，则只能将第r个数加入判断
}
return ret;
}
void update(int x, int val, int n) // 单单改变父亲结点是不够的，因为无法确定这段区间中的最大值来自哪里，
{
// 所以还需要与子区间进行比较确定最大值
a[x] = val;
for (int i = x; i <= n; i += lowbit(i))
{
maxVal[i] = a[i];
for (int j = 1; j < lowbit(i); j <<= 1)
{
maxVal[i] = max(maxVal[i], maxVal[i - j]);
}
}
}
int main()
{
int n, m, a, b;
while (~scanf("%d%d", &n, &m))
{
init(n);
char op[2];
for (int i = 0; i < m; ++i)
{
scanf("%s%d%d", op, &a, &b);
if (op[0] == 'Q') printf("%dn", getMax(a, b));
else update(a, b, n);
}
}
return 0;
}



练习地址：https://cn.vjudge.net/contest/179845

愿你一生清澈明朗，做您愿做之事，爱你愿爱之人!

复制代码
复制代码
复制代码