树状数组解析

为什么要搞树状数组？

我们先来看一个问题：

在区间[1,10000]上进行两种操作

操作A:把位置x的值+k

操作B:询问区间[l,r]所有数字之和

区间的初始值全部为0

操作A和操作B会被穿插着安排

如果我们每种操作都暴力进行，

那么显然总的时间复杂度为O(mA+n*mB)

如果我们使用树状数组，复杂度将会降低到O((mA+mB)*logn)

树状数组是个什么鬼？

一棵树(就是可以跳着更新的数组嘛),结点i存储的信息为i~1的后缀和。

有了后缀和可以干什么呢？就可以对任意区间和进行操作了啊……

总而言之，就是一个可以快速进行单点区间操作的树形结构。

树状数组的建立

首先我们要搞一个神奇的lowbit函数，这个函数有个??用啊？

这个lowbit是个什么骚操作呢，设当前数为x，lowbit（x）= x&-x,就这样，在我看来这就是个xjb乱搞出来的规律

这个函数可以说是树状数组的核心。

我们先来看看1~32的lowbit，

1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 16 1 2 1 4 1 2 1 8 1 2 1 4 1 2 1 32

我们让第i个位置管理[i-lowbit(i)+1,i]这一段区间

　下划线就是每个数可以管控的范围。

　接下来就是要对区间进行查询操作了

首先，我们发现当当前数lowbit等于1时可以管控前一个，当当前lowbit值为2时可以管控到前两个，以此类推。

　然后我们又发现当前位置减去它的lowbit恰好可以可以更新到前一个计算好的区间。好吧我承认这句话晦涩难懂

举个栗子

　当前位置是3，减去lowbit，3-1=2，此时1-2就是那个下一段区间，再更新，没有可以更新的了，输出答案。

　好吧可能你们还是没懂

大佬请自动忽略下一排

　再举个栗子

　当前位置是7，减去lowbit，7-1=6，此时5-6就是那个下一段区间，再更新，下一个区间结尾为4，在更新，没了，输出答案。

显然，我们可以看出要求数组的某个结点的话，可以一直减去当前点的lowbit并加上当前点的值。知道此时点的编号为零。

　再来谈谈区间更新，既然掌握了查询，那更新就不需要再过脑子比较容易了，更新了当前区间后，要把后面包含当前区间的所有区间更新，别忘了它还是个后缀和。

　更新依然会使用到lowbit,怎么样，这个lowbit很玄学强大吧？

　再次用到lowbit大法，一直向后加lowbit，直到达到区间的临界点。

　是不是看到到这里已经饥渴难耐了？那就别往下看了，滚去code

　talk is cheap，show me the coding

　代码

const int MAX_N = 10010;
int c_tree[MAX_N];//建立树状数组
int n;

int lowbit(int x)
{
   return x&(-x);//神奇的lowbit 
}

int getsum(int x)
{
      int res=0;
      while(x>0)
    {
       res += c_tree[x];
       x=x-lowbit(x);
    }//求当前结点 
    return res;
}

void change(int x,int c)
{
      while(x<=n)
      {
       c_tree[x]+=c;
　　　　x=x+lowbit(x);
    }//更新区间
}

ps：实在不懂的话可以把lowbit看作是一个迭代器，一个区间一个区间的迭代。

感谢知乎大佬的启发，我这个算是他的精简版吧：https://zhuanlan.zhihu.com/p/25185969

如需转载请注明地址及作者

数据结构树状数组

树状数组解析

相关

标签