树状数组主要用于查询任意两位之间的所有元素之和，而传统方法求区间和的方法如下：

 用一个sum数组来储存1-i之间的区间和，那么如果要求从i到j的区间和的话，就用sum[i]-sum[j]，此时算法复杂度为n.

但是传统方法中，如果要更新一个元素值，那么此时更新就要把所有包含这个元素的区间全部遍历一遍，即算法复杂度为n

那么整个算法的复杂度为n^2

所以我们发现了树状数组这个算法，将更新与查找的算法复杂度降低至logn

 

 

lowbit函数的工作是算出x的二进制的从右往左数第一个数的值

  1. 把6转换为二进制数110
  2. 从左往右数第一个1的位置
  3. 此时lowbit(6)就=二进制的10
  4. 将（10）2转换为十进制
  5. 返回2

lowbit函数如下：

  1. int lowbit(x){   
  2.     return x & -x;
  3. }

 

 那么这个代码是什么意思呢？

&是按位与，按位与的运算为：如果两个数均为1，则返回1，否则，返回0.

那么x&(-x)是怎么做到我们想要的预期的呢？

在电脑中的运算是这样的：

例如lowbit(6)

  1. 输入2788，并将其保存入x中
  2. 将x转换为二进制码101011100100
  3. 计算出1011的补码为0101011100100
  4. 通过补码计算出-x为1010100011100
  5. 按位与运算0000000000100

因此，我们得出按位与的运算和lowbit的运算时一样的。

 

我们用两个数组来保存树状数组的结构：

tree数组和ans数组

其中，ans数组为输入的元素值

而tree数组的生成就要靠ans数组了

如图，即为tree数组

 

上文说过，如果用传统方法来更新ans数组中的元素的话，会耗费大量的时间。那么我们不禁有个疑问了：树状数组是怎么缩短这个时间的呢？

例如，我们将ans[2]+3

那么我们将要更新1所在的所有区间。即：

我们需要更新所有的tree[2],tree[4],tree[8]的值

也就是说，当我们要对最底层的值进行更新时，那么它相应的父情节点储蓄的和也需要进行更新。

 

  1. void update(int index, int value){
  2.     // len是数组tree的长度,,index为需要更新的数的下标，value为要更新的值
  3.     while(index <= len){
  4.         tree[index] += value;
  5.         index += lowbit(index);
  6.     }
  7. }

 

 

 

 此代码复杂度为logn

 

在tree数组中，tree[i]并不表示1-i的区间和，而表示从i开始往前数lowbit(i)个数的区间和。

所以，我们需要一个算法来生成树状数组。

例如：查询从1-10的区间和：

这时，我们需要查找tree[8]+tree[10]的和

 

  1. int sum(int index)
    {
  2.     int result = 0;
  3.     while(index){
  4.         result += tree[index];
  5.         index -= lowbit(index);
  6.     }
  7.     return result;
  8. }

 

此操作的算法复杂度为logn

如果我们要计算tree中i-j的区间和，怎么办呢？

 

  1. int p_sum(int i, int j){
  2.     return sum(j) - sum(i) + Ans[i];
  3. }

 

算法复杂度为logn

 

posted on 2018-08-20 18:42 绝境狼王 阅读(…) 评论(…) 编辑 收藏

版权声明：本文为Wolfbeyond原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/Wolfbeyond/p/9451926.html