今天学了很多关于树状数组的技巧。一个是利用树状数组可以简单的实现段更新,点询问(二维的段更新点询问也可以),每次修改只需要修改2个角或者4个角就可以了,另外一个技巧就是这题,原本用线段树做,现在可以用树状数组做的题,只需多维护一个bit即可。具体的思路见下面的链接:
http://hi.baidu.com/billdu/item/053f6a15ca301b0a8ebde400
要理解里面的橙色块求的时候是打竖看的,不是打横看的。
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 |
#pragma warning(disable:4996) #include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<algorithm> #include<cmath> #include<string> #define ll long long #define maxn 100000 #define lowbit(k) k&(-k) using
namespace std; ll bit[2][maxn + 50]; int
n,q; void
inc(ll bit[], int
i, int
m) { for
(; i <= n; i += lowbit(i)) bit[i] += m; } ll query(ll bit[], int
i) { ll sum = 0; for
(; i > 0; i -= lowbit(i)){ sum += bit[i]; } return
sum; } ll sum[maxn + 50]; int
main() { while
(cin >> n >> q) { memset (bit, 0, sizeof (bit)); for
( int i = 1; i <= n; i++){ scanf ( "%lld" , sum + i); } sum[0] = 0; for
( int i = 1; i <= n; i++) sum[i] += sum[i - 1]; char
str[3]; int
a,b,c; for
( int i = 0; i < q; i++){ scanf ( "%s" , str); if
(str[0] == ‘Q‘ ){ scanf ( "%d%d" , &a, &b); ll ans = (query(bit[0], b)*(b + 1) - query(bit[1], b)) - (query(bit[0], a - 1)*a - query(bit[1], a - 1)); ans += sum[b] - sum[a - 1]; printf ( "%lld\n" , ans); } else { scanf ( "%d%d%d" , &a, &b, &c); inc(bit[0], a, c); inc(bit[1], a, c*a); inc(bit[0], b + 1, -c); inc(bit[1], b + 1, -c*(b + 1)); } } } return
0; } |
POJ3468 A Simple Problem With Integers 树状数组 区间更新区间询问
原文:http://www.cnblogs.com/chanme/p/3555084.html