树状数组主要是用来解决动态前缀和问题；一般来说，问题是这么问的：

给定一个数组，有m次操纵（选择数组中的一个元素并让其加v）以及q次询问（查询a[1]+a[2]+a[3]+…+a[x]的值）

如果用暴力的方法，每次操作的时间复杂的为O(1)，而每次查询的时间复杂度O(n)，n为数组的长度；

所以总的时间复杂度为O(qn)；显然不行，所以就用到了树状数组。

树状数组大概长这样：

我们知道，前缀和数组的每一位记录的是从开始到当前位置的所有元素的和，而树状数组也是类似的，

对于上图，节点4记录的是a[1]到a[4]的和,a[3]记录的是a[3]到a[3]的和，也就是a[3];树状数组是将数组分成了若干段，每次修改只需要改覆盖到当前节点的区间，例如要修改节点6的值，我们只需要更新a[6]、a[8]、a[16]；如果要查询某个位置的前缀和，例如节点11，我们只需要查询a[8]、a[10]、a[11]的值然后相加即可。

原理很简单，那现在问题来了，我们怎么知道要修改或者查询哪些区间呢？

我们是这么定义的：

对于某个位置x，那么x所覆盖的区间里元素的个数为 2^k 个（k指的是x二进制末尾0的数量）

例如：x==6，6的二进制为 110 末尾0的数量k=1，所以6的区间里元素个数为：2¹=2个

又如：x==8，8的二进制为 1000 末尾0的数量k=3，所以8的区间里元素的个数为：2³=8个

对于询问：

我们一般采用二进制拆分的方式，例如我们要询问13这个点的前缀和：

13的二进制为 1101 ，我们每次都会减去末尾1

1101₂ = 13

1100₂ = 12（1101-0001=1100）

1000₂ = 8（1100-0100=1000）

我们可以看到上面的图，13的前缀和等于：a[13]+a[12]+a[8]，正好跟上面操作所得到的结果是一样的。

对于修改：

我们将查询时的方法倒过来，每次都在末尾1的相同位置加上1（同一二进制位）

例如，我们要修改10这个点：

1010₂=10

1100₂=12（1010+0010=1100）

10000₂=16（1100+0100=10000）

对于10这个点，我们只需要修改节点10、12、16；

对于加减末尾1的这个操作，我们是这么实现的：

int lowbit(int x)
{
	return x & (-x);
}
//x+=lowbit(x)
//x-=lowbit(x)

为什么要这么写呢？

在计算机里，负数一般是用补码表示的，而补码指对原码的每一位进行取反，然后加1，比如-6，6的二进制是0110，而补码是 1010（0110 取反 1001+1=1010），我们对原码和补码进行与运算（&）就会得到x的末尾1；

原码：0110

补码：1010

&：= 0010

这里解释一下，我们刚刚说了，补码是对原码的每一位进行取反，这时候跟原码正好是反过来，如果这时候进行&运算结果为0，因为它们每一位都不同；但如果取反之后加1，那么在末尾一定会进1，那么除这一位以外，所有位都都没有相同的1

那最后看一下代码：

//数组a是要维护的数组，也就是树状数组
//n是数组a的长度
int lowbit(int x)
{
	return x & (-x);
}

int query(int x)//查询操作
{
	int res = 0;
	while (x)
	{
		res += a[x];
		x -= lowbit(x);
	}
	return res;
}
void add(int x, int v)//x这个位置加上v
{
	while (x<=n)
	{
		a[x] += v;
		x += lowbit(x);
	}
}