devbox
Gausst松鼠会
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

高级数据结构-树状数组总结_高级数据结构的学习与实现 树状数组

作者：Gausst松鼠会 | 2024-05-31 20:13:56

赞

踩

高级数据结构的学习与实现 树状数组

高级数据结构-树状数组总结

一维树状数组

1.更改单点，输出区间和
         一般用向上修改，向下统计， 也就是在updata函数里面使用+=，在 sum函数里面使用-=
         完整代码如下

  1. void updata(int x, int num)
  2. {
  3.     while (x <= n)   //树状数组的大小
  4.     {
  5.         bit[x] += num;
  6.         x += lowbit(x);    //lowbit返回2^k  函数内容为return x&-x;
  7.     }
  8. }
  1. int sum(int x)
  2. {
  3.     int sum = 0;
  4.     while (x > 0)
  5.     {
  6.         sum += bit[x];
  7.         x -= lowbit(x);
  8.     }
  9.     return sum;
  10. }


    例题如下 杭电 敌兵布阵
    题意就是对n个阵地中的某个，进行数目的加减操作，然后输出从a到b阵地的总人数。
    代码如下：

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <stack>
  6. #include <queue>
  7. #include <cmath>
  8. #include <map>
  9. #include <string>
  10. #include <cstdlib>
  11.  
  12. using namespace std;
  13. const int MAXN = 50000 + 10;
  14. int BIT[MAXN], t;
  15.  
  16. int lowbit(int x)
  17. {
  18.     return x&-x;
  19. }
  20.  
  21. void updata(int x, int num)
  22. {
  23.     while (x <= t)
  24.     {
  25.         BIT[x] += num;
  26.         x += lowbit(x);
  27.     }
  28. }
  29.  
  30. int sum(int x)
  31. {
  32.     int sum = 0;
  33.     while (x > 0)
  34.     {
  35.         sum += BIT[x];
  36.         x -= lowbit(x);
  37.     }
  38.     return sum;
  39. }
  40.  
  41. int main()
  42. {
  43.     #ifdef LOCAL
  44.         freopen("in.txt", "r", stdin);
  45.         //freopen("out.txt", "w", stdout);
  46.     #endif // LOCAL
  47.     int T;
  48.     int num, a, b;
  49.     int Ncase = 1;
  50.     scanf("%d", &T);
  51.     while (T--)
  52.     {
  53.         memset(BIT, 0, sizeof(BIT));
  54.         scanf("%d", &t);
  55.         for (int i = 1; i <= t; ++i)
  56.         {
  57.             scanf("%d", &num);
  58.             updata(i, num);    //单点更新
  59.         }
  60.         printf("Case %d:\n", Ncase++);
  61.         char command[10];
  62.         while (scanf("%s", command) != EOF)
  63.         {
  64.             if (command[0] == 'E')
  65.                 break;
  66.             scanf("%d%d", &a, &b);
  67.             if (command[0] == 'S')
  68.                 updata(a, -b);    //单点更新
  69.             else if (command[0] == 'A')
  70.                 updata(a, b);    //单点更新
  71.             else
  72.                 printf("%d\n", sum(b) - sum(a-1));    //返回总和 因为sum(b) 返回从1到b的值，然后 sum(a-1)返回从1到a-1的值 相减就是a到b的值。
  73.         }
  74.     }
  75.     return 0;
  76. }


2.更改区间，输出单点

    一般用向下修改，向上统计， 也就是在updata函数里面使用-=，在 sum函数里面使用+=
     完整代码如下

  1. void updata(int x, int num)
  2. {
  3.     while (x > 0)   
  4.     {
  5.         bit[x] += num;
  6.         x -= lowbit(x);    //lowbit返回2^k  函数内容为return x&-x;
  7.     }
  8. }

  1. int sum(int x)
  2. {
  3.     int sum = 0;
  4.     while (x <= n)    //树状数组的大小
  5.     {
  6.         sum += bit[x];
  7.         x += lowbit(x);
  8.     }
  9.     return sum;
  10. }



    例题如下杭电 Color the ball
    题意 在一段连续的区间上 从a到b依次 涂色 也就是值+1 然后输出某个单点的值
    代码如下

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <stack>
  6. #include <queue>
  7. #include <cmath>
  8. #include <map>
  9. #include <string>
  10. #include <cstdlib>
  11.  
  12. using namespace std;
  13. const int MAXN = 100000 + 10;
  14. int bit[MAXN], n;
  15.  
  16. int lowbit(int x)
  17. {
  18.     return x&-x;
  19. }
  20.  
  21. void updata(int x, int num)
  22. {
  23.     while (x > 0)
  24.     {
  25.         bit[x] += num;
  26.         x -= lowbit(x);
  27.     }
  28. }
  29.  
  30. int sum(int x)
  31. {
  32.     int sum = 0;
  33.     while (x <= n)
  34.     {
  35.         sum += bit[x];
  36.         x += lowbit(x);
  37.     }
  38.     return sum;
  39. }
  40.  
  41. int main()
  42. {
  43.     #ifdef LOCAL
  44.         freopen("in.txt", "r", stdin);
  45.         //freopen("out.txt", "w", stdout);
  46.     #endif // LOCAL
  47.     int a, b;
  48.     while (scanf("%d", &n) != EOF && n != 0)
  49.     {
  50.         memset(bit, 0 ,sizeof(bit));
  51.         for (int i = 1; i <= n; ++i)
  52.         {
  53.             scanf("%d%d", &a, &b);
  54.             updata(b, 1);    //单点更新
  55.             updata(a - 1, -1);    //单点更新
  56.         }
  57.         printf("%d", sum(1));    //因为单点更新的时候取+1, -1 相互抵消，所以sum(1）就是单点的值
  58.         for (int i = 2; i <= n; ++i)
  59.             printf(" %d", sum(i));
  60.         printf("\n");
  61.     }
  62.     return 0;
  63. }


    一维树状数组更新和求和可以在数轴上进行模拟，用区间来表示。理解更快。

二维树状数组

    二维树状数组在操作是，是以二维的直角坐标系为基准，在更新时应该注意边界问题

    1.单点更新，输出区间

     在updata里面使用 += 在Query里面使用-=

    实例如下

    

  1. void updata(int x, int y, int num)
  2. {
  3.     int temp = x;
  4.     while (y <= n)
  5.     {
  6.         x = temp;
  7.         while (x <= n)
  8.         {
  9.             bit[x][y] += num;
  10.             x += lowbit(x);
  11.         }
  12.         y += lowbit(y);
  13.     }
  14. }
  1. int Query(int x, int y)
  2. {
  3.     int sum = 0;
  4.     int temp = x;
  5.     while (y > 0)
  6.     {
  7.         x = temp;    //指针一定要初始化
  8.         while (x > 0)
  9.         {
  10.             sum += bit[x][y];
  11.              x -= lowbit(x);
  12.         }
  13.         y -= lowbit(y);
  14.     }
  15.     return sum;
  16. }
    例题 POJ Mobile phones
   题意 在一个已知的二维空间，输入命令1  表示 在 所指示的点加上指定的 数  输入命令2 则输出所指向的二维区间的和
    用向上更新，向下求和

    代码如下
   
    
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <stack>
  6. #include <queue>
  7. #include <cmath>
  8. #include <map>
  9. #include <string>
  10. #include <list>
  11. #include <vector>
  12. #include <cstdlib>
  13.  
  14. using namespace std;
  15. const int MAXN = 1250;
  16. int bit[MAXN][MAXN], n;
  17. int lowbit(int x)
  18. {
  19.     return x&-x;
  20. }
  21.  
  22. void updata(int x, int y, int num)
  23. {
  24.     int temp = x;
  25.     while (y <= n)
  26.     {
  27.         x = temp;
  28.         while (x <= n)
  29.         {
  30.             bit[x][y] += num;
  31.             x += lowbit(x);
  32.         }
  33.         y += lowbit(y);
  34.     }
  35. }
  36.  
  37. int Query(int x, int y)
  38. {
  39.     int sum = 0;
  40.     int temp = x;
  41.     while (y > 0)
  42.     {
  43.         x = temp;
  44.         while (x > 0)
  45.         {
  46.             sum += bit[x][y];
  47.              x -= lowbit(x);
  48.         }
  49.         y -= lowbit(y);
  50.     }
  51.     return sum;
  52. }
  53.  
  54. int main()
  55. {
  56.     #ifdef LOCAL
  57.         freopen("in.txt", "r", stdin);
  58.         //freopen("out.txt", "w", stdout);
  59.     #endif // LOCAL
  60.     int com;
  61.     int x, y, a, b;
  62.     while (scanf("%d", &com) != EOF && com != 3)
  63.     {
  64.  
  65.         if (com == 0)
  66.         {
  67.              scanf("%d", &n);
  68.              memset(bit, 0, sizeof(bit));
  69.         }
  70.         else if (com == 1)
  71.         {
  72.             scanf("%d%d%d", &x, &y, &a);
  73.             updata(x + 1, y + 1, a);    //单点向上更新
  74.         }
  75.         else
  76.         {
  77.             scanf("%d%d%d%d", &x, &y, &a, &b);
  78.             x++; y++; a++; b++;
  79.  
  80.             printf("%d\n", Query(a, b) - Query(a, y - 1) - Query(x - 1, b) + Query(x - 1, y - 1));   //向下求和   求和注意筛选区间以及边界问题
  81.         }
  82.     }
  83.     return 0;
  84. }

关于区间的筛选和边界  如图所示



2.区间更新，输出单点
    和一维的类似 ，在二维里面，仍然是用两个坐标之间的差值，代表所更新的区间，而坐标之间的差值，需要考虑，上图所示
   例子代码，就不写了，和一维类似，只是改变单点更新里面的大小。
    直接上例题：  POJ Matrix
   题意： 给定大小的矩阵中，C表示更新区段，Q表示，输入单点值  这里只有0和1 两种 所以采用累加 然后求和
    代码如下：
    
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <stack>
  6. #include <queue>
  7. #include <cmath>
  8. #include <map>
  9. #include <string>
  10. #include <cstdlib>
  11.  
  12. using namespace std;
  13. const int MAXN = 1010;
  14. int bit[MAXN][MAXN], n;
  15.  
  16. int lowbit(int x)
  17. {
  18.     return x&-x;
  19. }
  20.  
  21. void updata(int x, int y, int num)
  22. {
  23.     int temp = x;
  24.     while (y <= n)
  25.     {
  26.         x = temp;
  27.         while (x <= n)
  28.         {
  29.             bit[x][y] += num;
  30.             x += lowbit(x);
  31.         }
  32.         y += lowbit(y);
  33.     }
  34. }
  35.  
  36. int Query(int x, int y)
  37. {
  38.     int sum = 0;
  39.     int temp = x;
  40.     while ( y > 0)
  41.     {
  42.         x = temp;
  43.         while( x > 0)
  44.         {
  45.             sum += bit[x][y];
  46.             x -= lowbit(x);
  47.         }
  48.         y -= lowbit(y);
  49.     }
  50.     return sum;
  51. }
  52.  
  53. int main()
  54. {
  55.     #ifdef LOCAL
  56.         freopen("in.txt", "r", stdin);
  57.         //freopen("out.txt", "w", stdout);
  58.     #endif // LOCAL
  59.     int t, T;
  60.     int blank = 0;
  61.     int x1, x2, y1, y2;
  62.     scanf("%d", &T);
  63.     while (T--)
  64.     {
  65.         memset(bit, 0, sizeof(bit));
  66.         scanf("%d%d", &n, &t);
  67.         if (blank++ != 0)
  68.             printf("\n");
  69.         while (t--)
  70.         {
  71.             char command[3];
  72.             scanf("%s", command);
  73.             if (command[0] == 'C')
  74.             {
  75.                 scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
  76.                 updata(x1, y1, 1);
  77.                 updata(x2 + 1, y1, -1);
  78.                 updata(x1, y2 + 1, -1);
  79.                 updata(x2 + 1, y2 + 1, 1);     //更新时 区间的选用 参照上面的图片
  80.             } 
  81.             else
  82.             {
  83.                 scanf("%d%d", &x1, &y1);
  84.                 printf("%d\n", Query(x1, y1) % 2);
  85.             }
  86.         }
  87.     }
  88.     return 0;
  89. }


小结：  树状数组在应用时，关键在于，确定更新方式，以及更新区间



声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/654175
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号