树状数组区间更新+区间查询+单点查询
为了更好地使用复杂度比线段树更加优化的树状数组，所以必须实现树状数组的区间更新；树状数组时间复杂度为O(MlogN)， 实际用的时候优于线段树，且写得少。
区间更新、单点查询
引入差分数组，假设初始数据数组为a，另a[0] = 0；设要维护的差分数组为 d[i] = a[i] - a[i-1]；进一步可知 a[i] = d[1] + d[2] + ... + d[i]; 即前i项和，为方便记为sigma(d, i)；例如如下例子：
a：1 2 3 5 6 9
d：1 1 1 2 1 3
如果进行区间[2, 5]更新加2，则：
a：1 4 5 7 8 9
d：1 3 1 2 1 1
会发现当某个区间[x, y]内值发生了同等改变，但这个区间内的差值还是不变的，只有d[x]和d[y+1]的值发生了改变。
所以可以建立区间更新、单点查询的树状数组去维护d[]，例如如下例子：
d：1 1 1 2 1 3
c：1 2 1 5 1 4（c值如何计算参考下图）
区间[2, 5]更新加2，则：
d：1 3 1 2 1 1
c：1 4 1 7 1 2（c值如何计算参考下图）
int lowbit(int k){
return k & -k;
}
void update(int n, int *c, int i, int va){
while(i <= n){
c[i] += va;
i += lowbit(i);
}
}
int pointValue(int *c, int i) {
int res = 0;
while(i > 0){
res += c[i];
i -= lowbit(i);
}
return res;
}
//-------------------------------------
// 在区间[x, y]增加k
updata(n, c, x, k);
updata(n, c, y+1, -k);
// 获得第i点的值
pointValue(c, i);区间更新、区间查询
根据差分数组：
sum[n]
= a[1] + a[2] + .. + a[n];
= sigma(d, 1) + sigma(d, 2) + ... + sigma(d, n);
= n*d[1] + (n-1)*d[2] + ... + 2*d[n-1] + 1*d[n];
= n*(d[1] + d[2] +...+ d[n]) - (0*d[1] + 1*d[2] + ... + (n-1)*d[n]);
所以可以得到 sum[n] =n * sigma(d, n) - (0*d[1] + 1*d[2] + ... + (n-1)*d[n]);
令r[i] = (i-1) * d[i];
则 sum[n] = n * sigma(d, n) - sigma(r, n);
此时则需要构造两个树状数组去分别维护d[]和r[]的更新；例如如下例子：
a： 1 2 3 5 6 9
d： 1 1 1 2 1 3
c1：1 2 1 5 1 4
r： 0 1 2 6 4 15
c2：0 1 2 9 4 19
如果进行区间[2, 5]更新加2，则：
a： 1 4 5 7 8 9
d： 1 3 1 2 1 1
c1：1 4 1 7 1 2
r： 0 3 2 6 4 5
c2：0 3 2 11 4 9
注：c1、c2的计算过程同样参考上图。
注意c2更新前后，其在区间左端点2处开始向后更新加k*(2-1)，在右端点5再加1=6处，更新减k*(5-1)。
代码如下：
int lowbit(int k){
return k & -k;
}
void update(int n, int *c1, int *c2, int i, int va){
int x = i;
while(i <= n){
c1[i] += va;
c2[i] += va * (x-1);
i += lowbit(i);
}
}
int sum(int *c1, int *c2, int i) {
int res = 0, x = i;
while(i > 0){
res += x * c1[i] - c2[i];
i -= lowbit(i);
}
return res;
}
//-------------------------------------
// 在区间[x, y]增加k
updata(n, c, x, k);
updata(n, c, y+1, -k);
// 获得[x, y]的和
res = sum(c1, c2, y) - sum(c1, c2, x-1);
其它细节可参考：https://www.cnblogs.com/xenny/p/9739600.html