本文主要是介绍数据结构-树状数组讲解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
另外，对于求数列的前n项和，只需找到n以前的所有最大子树，把其根节点的C加起来即可。
不难发现，这些子树的数目是n在二进制时1的个数，或者说是把n展开成2的幂方和时的项数,
因此，求和操作的复杂度也是O(logn)。
接着，我们考察这两种操作下标变化的规律：
首先看修改操作：
已知下标i，求其父节点的下标。
我们可以考虑对树从逻辑上转化：
如图，我们将子树向右对称翻折，虚拟出一些空白结点（图中白色），将原树转化成完全二叉树。
有图可知，对于节点i，其父节点的下标与翻折出的空白节点下标相同。
因而父节点下标 p=i+2^k (2^k是i用2的幂方和展开式中的最小幂，即i为根节点子树的规模)
即 p = i + i&(i^(i-1)) 。
接着对于求和操作：
因为每棵子树覆盖的范围都是2的幂，所以我们要求子树i的前一棵树，只需让i减去2的最小幂即可。
即 p = i - i&(i^(i-1)) 。
至此，我们已经比较详细的分析了树状数组的复杂度和原理。
在最后，我们将给出一些树状数组的实现代码，希望读者能够仔细体会其中的细节。
【代码】
求lowbit(i)
int Lowbit(int t) { return t & ( -t ); } |
求前n项和：
int Sum(int i) { int sum = 0; while(i > 0) { sum += c[i]; i -= Lowbit(i); } return sum; } |
对某个元素进行加法操作：
void add(int i , int d)
{
while(i<= n)
{
c[i] += d;
i+= Lowbit(i);
}
}
这篇关于数据结构-树状数组讲解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
