高级数据布局-树状数组

先容

树状数组的推导

两个底子操纵

模板-acwing795. 前缀和

1. #include<bits/stdc++.h>
2. using namespace std;
4. const int N = 1e6+10;
5. int c[N];
7. int lowbit(int x){
8.         return x & -x;
9. }
11. int query(int x){
12.         int ans = 0;
13.         for(; x; x -= lowbit(x)) ans += c[x];
14.         return ans;
15. }
17. void add(int x,int y){
18.         for(; x <= N; x += lowbit(x)) c[x] += y;
19. }
21. int main(){
22.         int n,m; scanf("%d%d",&n,&m);
23.         for(int i = 1; i <= n; i++){
24.                 int num; scanf("%d",&num);
25.                 add(i,num);
26.         }
27.         while(m--){
28.                 int l,r; scanf("%d%d",&l,&r);
29.                 printf("%d\n",query(r)-query(l-1));
30.         }
31.         return 0;
32. }

复制代码

模板-acwing5910. 求逆序对

1. ​
3. #include<bits/stdc++.h>
4. using namespace std;
6. typedef long long LL;
7. const int N = 1e6+10;
8. LL c[N],a[N];
10. int lowbit(int x)  // 返回末尾的1
11. {
12.     return x & -x;
13. }
15. LL query(int x){
16.     LL ans = 0;
17.     for(; x; x -= lowbit(x)) ans += c[x];
18.     return ans;
19. }
21. void add(int x,int y){
22.     for(; x <= N; x += lowbit(x)) c[x] += y;
23. }
25. int main()
26. {
27.     LL ans = 0;
28.     int n; scanf("%d",&n);
29.     for(int i = 1; i <= n; i++){
30.         scanf("%d",&a[i]);
31.     }
32.     //倒序扫描，找值比当前这个数小但是先进入树状数组的数，即1-（a[i]-1）的和，加入ans（根据逆序对的定义构造的）
33.     for(int i = n; i >= 1; i--){
34.         ans += query(a[i]-1)-query(0);
35.         add(a[i],1);
36.     }
37.     printf("%lld\n",ans);
38.     return 0;
39. }
41. ​

复制代码

 P3374 【模板】树状数组 1 

1. #include<bits/stdc++.h>
2. using namespace std;
4. const int N = 1e6+10;
5. long long c[N];
7. int lowbit(int x){
8.         return x & -x;
9. }
11. long long query(int x){
12.         long long ans = 0;
13.         for(; x; x -= lowbit(x)) ans += c[x];
14.         return ans;
15. }
17. void add(int x,int y){
18.         for(; x <= N; x += lowbit(x)) c[x] += y;
19. }
21. int main(){
22.         long long n,m; scanf("%lld%lld",&n,&m);
23.         for(int i = 1; i <= n; i++){
24.                 long long x; scanf("%lld",&x);
25.                 add(i,x);
26.         }
27.         while(m--){
28.                 long long t,idx,x,l,r; scanf("%lld",&t);
29.                 if(t == 1){
30.                         scanf("%lld%lld",&idx,&x);
31.                         add(idx,x);
32.                 }else{
33.                         scanf("%lld%lld",&l,&r);
34.                         printf("%lld\n",query(r)-query(l-1));
35.                 }
36.         }
37.         return 0;
38. }

复制代码

P3368

1. #include <bits/stdc++.h>
2. using namespace std;
4. const int N = 1e6 + 10;
5. int n, m, c[N],a[N];
7. int lowbit(int x){
8.         return x & -x;
9. }
11. void add(int x, int y){
12.         for (int i = x; i <= n; i += lowbit(i)) c[i] += y;
13. }
15. int fn(int x){
16.         int cnt = 0;
17.         for (int i = x; i; i -= lowbit(i)) cnt += c[i];
18.         return cnt;
19. }
21. int main()
22. {
23.         cin >> n >> m;
24.         for (int i = 1; i <= n; i++){
25.                 cin >> a[i];
26.                 add(i, a[i] - a[i - 1]);
27.         }
28.        
29.         while (m--){
30.                 int t; cin >> t;
31.                 if (t == 1){
32.                         int x, y, k; cin >> x >> y >> k;
33.                         add(x, k); add(y + 1, -k);
34.                 }
35.                 else {
36.                         int x; cin >> x;
37.                         cout << fn(x) << endl;
38.                 }
39.         }
41.     return 0;
42. }

复制代码

例题

A. 数列操纵

思绪

模板题，套树桩数组的模板即可。留意开long long
代码

1. #include<bits/stdc++.h>
2. using namespace std;
4. const int N = 1e6+10;
5. long long c[N];
7. int lowbit(int x){
8.         return x & -x;
9. }
11. long long query(int x){
12.         long long ans = 0;
13.         for(; x; x -= lowbit(x)) ans += c[x];
14.         return ans;
15. }
17. void add(int x,int y){
18.         for(; x <= N; x += lowbit(x)) c[x] += y;
19. }
21. int main(){
22.         long long n,m; scanf("%lld%lld",&n,&m);
23.         for(int i = 1; i <= n; i++){
24.                 long long x; scanf("%lld",&x);
25.                 add(i,x);
26.         }
27.         while(m--){
28.                 long long t,idx,x,l,r; scanf("%lld",&t);
29.                 if(t == 1){
30.                         scanf("%lld%lld",&idx,&x);
31.                         add(idx,x);
32.                 }else{
33.                         scanf("%lld%lld",&l,&r);
34.                         printf("%lld\n",query(r)-query(l-1));
35.                 }
36.         }
37.         return 0;
38. }

复制代码

 B. 数星星 Stars

思绪

        这道题的求解思绪跟逆序对那道题差不多，都是利用树状数组去查1-x的和，但是这道题要思量好一种雷同交心的思绪，就是他要找左下角的星星个数，他输入时是按照y增序，y雷同时按照x增序给出，那么某个星星的品级就是x坐标1-x的星星个数，但是要留意的是这道题有大概会坐标会为0那么就会出现越界题目，以是每次要给x坐标+1，但是团体每个数的巨细关系并不会改变。
代码

1. #include<bits/stdc++.h>
2. using namespace std;
4. const int N = 1e6+10;
5. long long c[N],lv[N];
7. int lowbit(int x){
8.         return x & -x;
9. }
11. long long query(int x){
12.         long long ans = 0;
13.         for(; x; x -= lowbit(x)) ans += c[x];
14.         return ans;
15. }
17. void add(int x,int y){
18.         for(; x <= N; x += lowbit(x)) c[x] += y;
19. }
21. int main(){
22.         int n; cin >> n;
23.         for(int i = 1; i <= n; i++){
24.                 int x,y; cin >> x >> y;
25.                 x++;
26.                 int t = query(x);
27.                 lv[t]++;
28.                 add(x,1);
29.         }
30.         for(int i = 0; i < n; i++) cout << lv[i] << endl;
31.         return 0;
32. }

复制代码

C. 校门外的树

思绪

        这道题由于是求某个区间内树的数目，树在区间内的具体位置是不知道的，以是用两个数组分别表现该点左侧树的数目和该点右侧树的数目，区间[a,b]内树的数目=b点左侧树的数目 – (a-1)点右侧树的数目。之以是是a-1点不是a点是由于要算上a点上的树。
代码

1. #include <bits/stdc++.h>
2. using namespace std;
3. int const N = 50010;
4. int n, m;
5. // 树状数组模板
6. int c1[N], c2[N];
8. #define lowbit(x) (x & -x)
9. typedef long long LL;
11. void add(int c[], int x, int v) {
12.     while (x < N) c[x] += v, x += lowbit(x);
13. }
15. LL sum(int c[], int x) {
16.     LL res = 0;
17.     while (x) res += c[x], x -= lowbit(x);
18.     return res;
19. }
21. //这道题因为是求某个区间内树的数量，树在区间内的具体位置是不知道的
22. //所以用两个数组分别表示该点左侧树的数量和该点右侧树的数量
23. //区间[a,b]内树的数量=b点左侧树的数量 – (a-1)点右侧树的数量。之所以是a-1点不是a点是因为要算上a点上的树。
25. int main() {
26.     int k, l, r;
27.     scanf("%d%d", &n, &m);
28.     for (int i = 1; i <= m; i++) {
29.         scanf("%d%d%d", &k, &l, &r);
30.         if (k == 1)
31.             add(c1, l, 1), add(c2, r, 1); // c1记录左括号的个数，c2记录右括号的个数
32.         else
33.             printf("%d\n", sum(c1, r) - sum(c2, l - 1));
34.     }
35.     return 0;
36. }

复制代码

D. 盘货人数

思绪

        模板题，直接套模板。开long long
代码

1. #include<bits/stdc++.h>
2. using namespace std;
4. const int N = 1e6+10;
5. long long c[N],lv[N];
7. int lowbit(int x){
8.         return x & -x;
9. }
11. long long query(int x){
12.         long long ans = 0;
13.         for(; x; x -= lowbit(x)) ans += c[x];
14.         return ans;
15. }
17. void add(int x,int y){
18.         for(; x <= N; x += lowbit(x)) c[x] += y;
19. }
21. int main(){
22.         int n,k; cin >> n >> k;
23.         for(int i = 1; i <= k; i++){
24.                 char t;
25.                 int m,p;
26.                 cin >> t;
27.                 if(t == 'A'){
28.                         scanf("%d",&m);
29.                         printf("%d\n",query(m));
30.                 }else if(t == 'B'){
31.                         scanf("%d%d",&m,&p);
32.                         add(m,p);
33.                 }else {
34.                         scanf("%d%d",&m,&p);
35.                         add(m,-p);
36.                 }
37.         }
38.         return 0;
39. }

复制代码

 E. 简单题

思绪

        这道题大概是这几道题中较难的一道，这道题如果不是取反操纵的话，就是一道树状数组区间修改区间查询的题了，但是他是取反操纵，我们就可以简化一下，不消像区间修改一样另开一个前缀和数组，接下来解说本体思绪：
        根据差分头脑，可以在从1~l先取反一次，再在1~r+1取反一次就可以得到l-r取反了，取反操纵就异或上1即可（^1），求某一位的值即从1~x的异或值就第x位的值。

1. #include<bits/stdc++.h>
2. using namespace std;
4. const int N = 1e6+10;
5. bool c[N];
6. int n,m;
8. int lowbit(int x){
9.         return x & -x;
10. }
12. bool query(int x){
13.         bool ans = 0;
14.         for(; x; x -= lowbit(x)) ans ^= c[x];
15.         return ans;
16. }
18. void add(int x){
19.         for(; x <= N; x += lowbit(x)) c[x] ^= 1;
20. }
22. void modify(int l, int r) // 原数组的区间修改 <- 差分数组的单点修改
23. {
24.         add(l);
25.         if (r != n)
26.                 add(r+1);
27. }
29. int main(){
30.         cin >> n >> m;
31.         for(int i = 1; i <= m; i++){
32.                 char t;
33.                 int x,l,r;
34.                 cin >> t;
35.                 if(t == '2'){
36.                         scanf("%d",&x);
37.                         printf("%d\n",query(x));
38.                 }else{
39.                         scanf("%d%d",&l,&r);
40.                         modify(l,r);
41.                 }
42.         }
43.         return 0;
44. }

复制代码