树状数组（超详细）

      树状数组(binary indexed tree，发明者Peter M.Fenwick 1994)，是一种设计新鲜的数组结构，它能够高效地获取数组中连续 k 个数的和。

        概括说，树状数组通常用于解决以下问题：

        数组A中的元素可能不断地被修改，怎样才能快速地获取连续几个数地和？

介绍

什么是树状数组？

我们给定一个数组A[ ]，我们设一个数组C[ ]满足

C[2]=A[1]+A[2]" role="presentation" style="position: relative;">C[2]=A[1]+A[2]$C[2]=A[1]+A[2]$

C[4]=A[1]+A[2]+A[3]+A[4]" role="presentation" style="position: relative;">C[4]=A[1]+A[2]+A[3]+A[4]$C[4]=A[1]+A[2]+A[3]+A[4]$

C[6]=A[5]+A[6]" role="presentation" style="position: relative;">C[6]=A[5]+A[6]$C[6]=A[5]+A[6]$

C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8]" role="presentation" style="position: relative;">C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8]$C[8]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7]+A[8]$

……

那么C数组就是树状数组。

思考：

实际上，我们设 k" role="presentation" style="position: relative;">k$k$ 为（下标）对应二进制末位0的个数， 从 1" role="presentation" style="position: relative;">1$1$ 开始算！

那么：

那么，问题来了给定，如何求2k" role="presentation" style="position: relative;">2k$2^k$？

答案很简单： & (−i)" role="presentation" style="position: relative;">(−i)$(-i)$。

关于 & (−i)" role="presentation" style="position: relative;">(−i)$(-i)$：

比如对于“010101000”最末有3个0，k" role="presentation" style="position: relative;">k$k$ 的值应该是3，算出的2k" role="presentation" style="position: relative;">2k$2^k$应该为8

110101000    ->     这是-i的原码

101010111     ->     这是-i的反码

101011000     ->     这是-i的补码

010101000     ->     这是i的补码

000001000     ->     这是(i & (-i))

。

我们定义它为lowbit(x)=x" role="presentation" style="position: relative;">lowbit(x)=x$lowbit(x)=x$&。

c++简短函数代码：

int lowbit(int x){
    return x & (-x);
}

求和：

当我们求A[1]+...+A[x]" role="presentation" style="position: relative;">A[1]+...+A[x]$A[1]+...+A[x]$的之和时，

如果包含的不一定是1...x" role="presentation" style="position: relative;">1...x$\mathrm{1...}x$的全部和，（比如C[6]=A[5]+A[6]" role="presentation" style="position: relative;">C[6]=A[5]+A[6]$C[6]=A[5]+A[6]$）就需要再找一个（显然k<x" role="presentation" style="position: relative;">k<x$k<x$）累加起来，这个k" role="presentation" style="position: relative;">k$k$我们称之为的前驱，举个例子：

A[1]+A[2]+...+A[6]=C[6]+C[4]" role="presentation" style="position: relative;">A[1]+A[2]+...+A[6]=C[6]+C[4]$A[1]+A[2]+...+A[6]=C[6]+C[4]$

前驱的编号即为比自己小的，最近的，最末连续0比自己多的数

所以的前驱k=x−lowbit(x)" role="presentation" style="position: relative;">k=x−lowbit(x)$k=x-lowbit(x)$，相当于剪掉了自己最左边的1

求和函数：，代码如下：

int getSum(int x){
    int ans = 0;
    for(int i = x; i > 0; i -= lowbit(i)) ans += C[i];
    return ans;
}

直接用一个循环求得Sum，时间复杂度为O(logn)" role="presentation" style="position: relative;">O(logn)$O(logn)$。

求区间之和怎么办？

getsum(y)−getsum(x−1)" role="presentation" style="position: relative;">getsum(y)−getsum(x−1)$getsum(y)-getsum(x-1)$！

修改：

修改了某个 ，就需要改动所有包含A[j]" role="presentation" style="position: relative;">A[j]$A[j]$的

从图上看就是要更改从叶子节点到根节点路径上所有的

怎么求一个节点的父节点？

经过观察和探究，前人们得出了这个规律：
父亲：比自己大的，最近的，末位连续0比自己多的数

节点父亲的编号=x+lowbit(x)" role="presentation" style="position: relative;">=x+lowbit(x)$=x+lowbit(x)$

修改函数：

void modify(int x, int d){
    for(int i = x; i <= n; i += lowbit(i)) C[i] += d;
}

其时间复杂度依旧为O(logn)" role="presentation" style="position: relative;">O(logn)$O(logn)$

一个小小的问题：

那原本的数组，应该怎么做：

其实调用修改函数，相当于把没有修改为一个值，代码如下。

cin >> n;
for(int i = 1; i <= n; i++){
	cin >> x;
	modify(i, x);
}

小结：

1、在很多情况下，线段树都可以用树状数组实现，凡是能用树状数组实现的一定能用线段树。

2、当题目不满组减法原则的时候，就只能用线段树，不能用树状数组。

3、树状数组的时间复杂的每一个操作都是O(logn)" role="presentation" style="position: relative;">O(logn)$O(logn)$的时间复杂度。

这篇文章就在一个代码中结束了！

觉得博主写的不错的关注支持一下吧！我会继续努力的~