一.引言——动态前缀和
前缀和求解我会在最后给出，想看的直接翻到最后，这里默认大家都知道前缀和怎么求解。
有这么一个场景，我们需要不断修改数组中的元素，并且问我们数组内某个区间的和。如果使用最原始的前缀和来求解，每次我们都要重新求一遍sum[]，更新时间复杂度是O（n）的，查询是O（1）的。
有没有什么办法能够平衡一下让时间复杂度更低，这就引入了树状数组的概念。
二.树状数组
1.介绍
我们最原始的想法是这样的，我们给数组分块，比如一个长度为16的数组，我们给它2个元素分一组，这样我们修改元素的时候可以只修改一个模块就行，其他模块不用修改。这样我们在求某个区间的元素的话，只需要将单个元素和模块相加就行了。
想到这，我们在进一步，我们是不是可以多分几个组，先1个分一组，再2个分一组，再4个分一组，再8个，再16个，将这个数组都存一遍，这样求和的时候就不用一个一个去将小模块加在一起。
从上面举的例子我们可以发现其实有一些模块是用不到的，删除它们
为什么用不到？
比如我们求前两个元素的元素和，直接使用14这个模块即可，不用使用到6。
再比如为什么14模块后面的5用不到，因为求前三个元素的元素和可以使用14+1，求前四个元素的元素和可以使用19。
将上面元素依次排成一个数组，这个数组就是树状数组。
看到这里可能有人会问：这是什么跟什么呀，为什么是这样？接下来我来告诉大家这个分组到底是怎么来的。
其实这个分组是根据下标的二进制来分出来的：
比如5的二进制的101，101就是4+1，所以0-5的区间可以分成一个长度为4的模块和长度为1的模块，对应上面的图是这样的：
看到这里大家不免有一个疑惑，这个树状数组tree[i]到底表示什么？
给大家看另一个图：
这个图对比较清晰的表示tree[]是什么，这里的c[]就是tree[]。
树状数组更新和查询的时间复杂度都是O（log N）的。
2.更新操作
我们想要更新数组内某个元素的值，更新完后肯定是要更新区间内的值的，那我们怎么更新呢？
比如我们要更新11这个下标的数，从图上我们也能看到，我们要跟新的区间是c[11]、c[12]、c[16]对不对。我们可以从这几个下标中找找关系。
这里就直接说结论了，实际证明比较麻烦，感兴趣的可以自己找找。
我们每次求的模块的下标就是当前下标+当前下标的lowbit。
什么是lowbit？lowbit(x)指的是x二进制最低位代表什么数字。
public void update(int index, int val) {
int delta = val - nums[index];
nums[index] = val;
for (int i = index + 1; i < tree.length; i += i & -i) {
tree[i] += delta;
}
}3.查询操作
这里给出查询前i个元素的元素和的方法：
int count(int p){
//求前q个元素的元素和
int result=0;
while(p!=0){
result+=tree[p];
p-=lowbit(p);
}
return result;
}4.核心代码
public int lowbit(int x){
return x&(-x);
}
public void update(int index, int val) {
//将下标index位置的元素改成val
int delta = val - nums[index];
nums[index] = val;
for (int i = index + 1; i < tree.length; i += i & -i) {
tree[i] += delta;
}
}
int count(int p){
//求前q个元素的元素和
int result=0;
while(p!=0){
result+=tree[p];
p-=lowbit(p);
}
return result;
}三.补充——前缀和
以往我们要得到某个范围内的全部元素和通过遍历，一个一个加起来，如果只是这么操作一次还好，要是多次操作时间复杂度就很高了。前缀和通过预处理一个数组，可以让我们快速的得到某个范围内的元素和。这个范围既可以是一维的，也可以是二维的。
1.一维前缀和
定义一个sum数组，大小是nums数组长度+1，sum[i]表示nums前 i 个数的总和。
预处理方法也是很简单：
int n=nums.length;
int[] sum=new int[n+1];
for (int i = 0; i < n; i++) {
sum[i+1]=sum[i]+nums[i];
}为什么sum的大小要比nums大1？其实就是为了方便我们处理。
有了这个sum数组，那我们这么求任意区间内元素的总和呢？
举个例子：
我们要求区间5-9的元素总和
sum[10]=nums[0]+nums[1]+...+nums[9]
sum[5]=nums[0]+nums[1]+...+nums[4]
区间5-9的总和=nums[5]+nums[6]+...+nums[9]=sum[10]-sum[5]
所以说任意区间 l-r 的元素总和等于：
sum[r+1]-sum[l]2.二维前缀和
定义一个二维sum数组，sum[i][j]表示nums[0][0]-nums[i-1][j-1]这个子矩阵（左上角是(0,0)，右下角是(i-1,j-1) ）的元素总和。
预处理方法：
int n= nums.length;
int m=nums[0].length;
int[][] sum=new int[n+1][m+1];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
sum[i+1][j+1]=sum[i+1][j]+sum[i][j+1]-sum[j][j]+nums[i][j];
}
}求子矩阵的和：
子矩阵的左上角是(l1,r1)，右下角是(l2,r2)，这个子矩阵的元素和是：
sum[l2+1][r2+1]-sum[l2+1][r1]-sum[l1][r2+1]+sum[l1][r1]四.补充——差分
如果我们想给某一个区间上的全部元素全都加上某个数，我们可以遍历一遍这个数组，给区间上的每个数加上。但是如果我们频繁的进行这些操作的话效率就太低了。差分通过预处理一个数组d，可以高效对某个区间内的元素加减某个数。
1.一维差分
定义一个数组d，d[i]=nums[i]-nums[i-1]（i>=1），特别的，当i=0时，d[0]=nums[0]。同时d的长度也是nums长度+1。如果将未经过处理的d从头累加起来的话就能还原原来的nums数组。
预处理d：
int n=nums.length;
int[] d=new int[n+1];
d[0]=nums[0];
for (int i = 1; i <= n; i++) {
d[i]=nums[i]-nums[i-1];
}我们想对l和r区间的元素同时加上val：
d[l]+=val;
d[r+1]-=val;
//更新nums
int sum=0;
for (int i = 0; i < n; i++) {
sum+=d[i];
nums[i]=sum;
}如果想减掉val的话将加减变一下就行了。
为什么这样写就可以实现对区间内的元素相加减呢？
前面说个将没处理d累加起来就等于原来的nums数组。我们在 l 位置时多加了一个val，那么从 l 开始的往后所有元素都要加上一个val。那我们想让 r 后面的元素不要加上val，那我们就在 r+1 的位置减去一个val，这样从 r+1 开始往后的全部元素都要减去一个val，这样就抵消了。
为什么将没处理d累加起来就等于原来的nums数组？
d[0]=nums[0]，d[1]=nums[1]-nums[0]，d[2]=nums[2]-nums[1]......
累加起来，nums[i]=d[i]+d[i-1]+...+d[0]。
2.二维差分
预处理：
int[][] d=new int[n+1][m+1];
for (int i = 1; i <=n; i++) {
for (int j = 1; j <= m; j++) {
d[i+1][j+1]+=nums[i][j];
d[i+1][j]-=nums[i][j];
d[i][j+1]-=nums[i][j];
d[i][j]+=nums[i][j];
}
}对左上角(x1,y1)与右下角(x2,y2)子矩阵内的元素同时加上val：
d[x1][y1] += val;
d[x2 + 1][y1] -= val;
d[x1][y2 + 1] -= val;
d[x2 + 1][y2 + 1] += val;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
nums[i][j] = nums[i - 1][j] + nums[i][j - 1] - nums[i - 1][j - 1] + d[i][j];
}
}