树状数组总结

第一次接触树状数组是大一时候还在企图搞算法竞赛的时候，但那个时候也没什么心思花在上面，没搞懂过，只是抄抄模板水水过。现在为了考研明年要考PAT，开始刷PAT题库了而且碰到这种题目了，没办法了，只能学一下了。也不是很深入，但是我觉得用用是够了。下面是介绍。

一.树状数组要解决的问题：

    有过算法学习经验的人应该都知道POJ一道经典的区间求和题，是的树状数组可以解决，区间的更新，区间的求和还有求前缀和的问题，因为他的查询和修改复杂度都是logN，效率很高。

二.树状数组是什么：

     其实就是叫二叉索引树，目的就是把线性结构的数组变成树状结构。如下图所示

其中最小面的圆圈表示一个数组，分别是123456，然后上面的圆圈表示和他相连的圆圈的和。我们可以看出，通过这些节点的加减，我们可以得出一个数组里连续几个数字的和。然后后面几个数字的和都可以由这几个数字的和相加。

我们把这些记录一小段一小段区间的和存在一个数组里面，命名为TreeArr,我们先这样想，我们如何去理解他们完成一中提到的功能。

1.对于区间求和，我们仅需要确定起始位置和结束位置，比如i和j，我们可以得出和就是从第一个到第j个元素的和减去从第一个到第i-1个元素的和。那么如何求第一个元素开始到最后一个元素的和呢，我们如何求TreeArr呢？

2.对于TreeArr的初始化，我们又该如何进行呢，要按什么规律去做？

三.lowbit函数

代码如下：

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

这个函数是干嘛用的呢？学过C语言的应该都知道的&的意思是异或，这个函数的作用是返回一个数用二进制表示后，最后一个1的位置，拿6举例，用二进制表示为

6=110

然后6&-6等于之后等于2.就是最后一个1的位置。

四.树状数组的区间和如何查询？

我们可以把6=110拆成，110=100+10；100是多少？4，10是多少？2.然后去观察上图，正好是这样。前面4个构成一组，后面2个构成一组。这也就是lowbit返回出来的位置拆开来。这里需要去体会一下，那么我们就找到了规律了。我们只需要从树的最高处往下累加到最后一层非叶子节点即可，按照lowbit(goal)的间隔去累加即可，goal为你要查的目标。代码如下：

int sum(int x, int *c) {
	int res = 0;
	while (x > 0) {
		res += c[x];
		x -= lowbit(x);
	}
	return res;
}

五.树状数组的维护？

光知道查询肯定没用的，我们需要维护这个树状数组的。不然就没有TreeArr，又怎么会有查询呢。

其实到这里一般都有想法了，上面查询是从上而下照下来，那么这里和就从下而上加上去就行了，我们可以知道上面的数组各项并不都与一个数的改变有关系，那么我们只需要把和它相关的TreeArr修改了就行了。代码如下；

void update(int x, int data, int *c,int size) {
	while (x <= size) {
		c[x] += data;
		x += lowbit(x);
	}
}

这样就实现了所有操作了。但是我们仍然需要知道这个不能做到的事情。比如动态的更新，还有只能用于求和的局限性。