树状数组(详细分析+应用)，看不懂打死我!

在学习一个算法之前一定要清楚它能干嘛，能解决什么样的问题，对你解题是否有帮助，然后才去学习它!

那么接下来看如下几个问题

顾名思义就是一个结构为树形结构的数组，于二叉树的结构类似但又不同，它是在二叉树的结构上删除了一些中间节点，来看两幅图就明白了.

1.这是二叉树的结构 2.这是树状数组的结构 不难发现，树状数组相比于二叉树删除了一些节点，但是为什么要删除呢？这就和树状数组的一些性质(lowbit)有关了，不懂没关系，继续往下看.

可以解决大部分区间上面的修改以及查询的问题，例如1.单点修改，单点查询，2.区间修改，单点查询，3.区间查询，区间修改，换言之，线段树能解决的问题，树状数组大部分也可以，但是并不一定都能解决，因为线段树的扩展性比树状数组要强.

有人会问了既然线段树的问题能够用树状数组解决而且线段树还比树状数组扩展性强，那为什么不直接用线段树呢？问的很好，树状数组的作用就是为了简化线段树，举个例子：一个问题可以用线段树解决写代码半个小时，但是用树状数组只需要10分钟，那么你会选择哪一个算法呢?没错，基于某些简单的问题，我们没必要用到功能性强但实现复杂的线段树(杀鸡焉用宰牛刀).

优点：修改和查询操作复杂度于线段树一样都是logN,但是常数比线段树小，并且实现比线段树简单

缺点：扩展性弱，线段树能解决的问题，树状数组不一定能解决.

如何计算一个非负整数n在二进制下的最低为1及其后面的0构成的数？ 例如： 44 = ( 101100 ) 2 44=(101100)_2 44=(101100)2​,最低为1和后面的0构成的数是 ( 100 ) 2 = 4 (100)_2=4 (100)2​=4 所以 l o w b i t ( 44 ) = l o w b i t ( ( 101100 ) 2 ) = ( 100 ) 2 = 4 lowbit(44)=lowbit((101100)_2)=(100)_2=4 lowbit(44)=lowbit((101100)2​)=(100)2​=4,那么lowbit运算时怎么实现的呢？

44的二进制=(101100)，我们对44的二进制数取反+1，也即~44+1,得到-44

-44的二进制=(010100)，然后我们把44和-44的二进制进行按位与运算，也即按位&得到,二进制000100，也就是十进制的4

所以lowbit(x) = x&(-x)

显然，我们一开始会想到暴力的朴素做法，单点修改操作时间复杂度O(1)，区间求和，暴力遍历区间每一个数再相加时间复杂度O(n)，如果区间求和查询的次数为n次，那么中的时间复杂度为O( n 2 n^2 n2),对于大数据的题来说肯定会T，此时如果用树状数组的话复杂度可以讲到O(nlogn).

接下来分析树状数组的原理 上面时树状数组的结构图，t[x]保存以x为根的子数中叶子节点值的和,原数组为a[] 那么原数组前4项的和t[4]=t[2]+t[3]+a[4]=t[1]+a[2]+t[3]+a[4]=a[1]+a[2]+a[3]+a[4],看似没有什么特点，别着急往下看

我们通过观察节点的二进制数，进一步发现，树状数组中节点x的父节点为x+lowbit(x),例如t[2]的父节点为t[4]=t[2+lowbit(2)]

所以我们在单点修改的同时，更新父节点就变得尤为简单，，例如我们对a[1]+k，那么祖先节点t[1],t[2],t[4],t[8]都需要+k更新(因为t[]表示前缀和)，此时我们就可以用lowbit操作实现. 代码