树状数组介绍

首先我们需要知道树状数组可以维护一些什么值，树状数组主要维护的值就是区间的前缀和。因此普通的树状数组需要满足结合律和可差分的性质。比如乘法、加法、异或。
然后就是树状数组是怎么把区间差分为不重不漏的子区间的呢。
首先我们假设一个数x的二进制位里面包含1的位置为\(a_{i_1},a_{i_2}...a_{i_n\).也就是\(x=2^{i_1}+2^{i_2}+...+2^{i_n}\)所以我们可以将这个区间[1,x]拆分为：
1.长度是\(2^{i_1}的小区间[1,2^{i_1}]\)
2.长度是\(2^{i_2}\)的小区间\([2^{i_1+1},2^{i_1}+2^{i_2}]\)
.......
n.长度为\(2^{i_n}\)的小区间\([2^{i_1}+2^{i_2}+....2^{i_{n-1}}+1,2^{i_1}+2^{i_2}+...+2^{i_n}]\)
然后比如求区间长度就可以使用lowbits函数就好了，因此我们可以得出来c[x]管辖的去区间是[l(x),x].其中\(l(x)=x-lowbits(x)+1\).
因此我们如果需要查询某一个区间就可以不断地减去lowbits(x)然后得到他管辖的那个子区间。
所以区间查询就暂时搞定了。
那么单点修改呢：
单点修改其实就是区间查询的你操作，就是不断得到往前面递推出来他的其他的管辖区间。也就是一个是减，一个是加。我们可以看下下面这张图：

我们一定需要注意的是单点修改才是建树的过程，查询的一个过程并不是哦。我们可以发现通过这样子的建树使得管辖的区间并没有重复和遗漏。
这里我们可以知道一个很重要的性质：

也就是上面所说的管辖的区间是没有重复和遗漏的，这也就使得我们在修改的时候并不会出现某一个点对其他的区间重复贡献了的问题。
一定要注意我们查询和我们的建树过程是不一样，比如查询7(111)->6(110)->4(100)->0.我们可以发现这是不会出现查询了4还会查询他的子区间2的情况的
这还是很神奇的，其实主要是我们第一步也就是将x划分\(2_i\)的子区间是正确的，而我们建树的过程就是划分区间的一个逆过程，也就是从后面往前面递推。所以这个也是正确的，并且修改和查询出来的结果都是不重复不遗漏的。

相关用途

下面讲述下他的一个用途：
(1)求区间的前缀和，异或和。还有一个需要知道的地方就是如果是区间修改，那么我们就需要看可不可以转换为对应的差分操作。
(2)树上做差分，以及差分和dp相结合。
(3)就是转换为对应的权值树状数组。
什么是权值树状数组呢：

其实权值树状数组维护的是一个相对的关系，所以一般都需要使用离散化。
离散化
这个的用途一般有求逆序对....

特殊性质

其实树状数组也是可以维护不可以差分的情况的，具体的看这篇博客把。
不可差分

时间复杂分析

这个我们理解了算法的本质之后就可以发现建树也就是add操作和ask都是logn的时间度，但是因为需要查询n个点所以总的时间复杂度是O(nlogn).