【算法思想篇】树状数组区间修改，区间查询

树状数组进阶：

区间修改与区间查询

今天老糊涂了，树状数组忘记了，基本的只要单点修改+区间查询功能，如果要进行区间加操作，需要把树状数组进行改造。

我们首先来回顾树状数组的功能：

lowbit(x&(-x))：返回二进制最低位1的值：比如x=1010那么lowbit值为2。

x+lowbit(x)：把最后一位二进制最低位1，往前进一位。

x-lowbit(x)：去掉最后一位二进制最低位1。

我们认为凡是x+lowbit(x)代表父亲节点，x-lowbit(x)代表儿子节点。

存储过程：

for (int i=x;i<=n;i+=lowbit(i)){

      sum[i]+=w;

}

我们只把值存储加在父亲节点上。

对于任何一个1-n的值，我们都可以通过这样存储在这样一个树形结构上面。

C1 = A1

C2 = A1+A2

C3 = A3

C4 = A1+A2+A3+A4

C5 = A5

C6 = A5+A6

C7 = A7

 C8 = A1+A2+A3+A4+A5+A6+A7+A8

区间求和：

对于需要求一个区间和[1-n]值，我们以及知道当前节点存储了当前的信息和之前的部分信息，因此我们需要往下不断寻找，而子节点的信息没有父亲节点的信息，从而不断往下查找从而得到答案。

区间修改：这个以及不能把树状数组再这么更新了，我们知道如果我更新，虽然也会起到区间更新的效果，但本质却并没有对后面产生影响，只不过对区间和产生影响罢了。

下面来介绍新的树状数组方法：

引入差分概念：

c[i]=a[i]-a[i-1]

那么我对某个区间内部+K实际上等价于区间内部所有c[i]+5

那么某个元素的值其实等于a[i]=∑n1c[i]a[i]=∑1nc[i]

那么区间和呢？

我们可以知道

∑n1a[i]∑1na[i]

=a[1]+a[2]+a[3]...a[n]=a[1]+a[2]+a[3]...a[n]

=a[1]+a[2]+a[3]...a[n]=a[1]+a[2]+a[3]...a[n]

=c[1]+c[1]+c[2]+c[1]+c[2]+c[3]...c[1]+c[2]...+c[n−1]+c[n]=c[1]+c[1]+c[2]+c[1]+c[2]+c[3]...c[1]+c[2]...+c[n−1]+c[n]

=c[1]+c[1]+c[2]+c[1]+c[2]+c[3]...c[1]+c[2]...+c[n−1]+c[n]=c[1]+c[1]+c[2]+c[1]+c[2]+c[3]...c[1]+c[2]...+c[n−1]+c[n]

=n∗(c[1]+c[2]+...+c[n])−(c[2]+c[3]+....c[n]+c[3]+...c[n]+...+c[n]+c[n])=n∗(c[1]+c[2]+...+c[n])−(c[2]+c[3]+....c[n]+c[3]+...c[n]+...+c[n]+c[n])

=n⋅∑n1c[i]−∑n1c[i]∗(i−1)=n⋅∑1nc[i]−∑1nc[i]∗(i−1)

=∑n1c[i]∗(n−i+1)=∑1nc[i]∗(n−i+1)

因此我们需要维护两个值:差分数组c[i]=a[i]-a[i-1]和b[i]=(c[i])*(i-1)

单点更新：

C[i]还是与原来的树状数组一样更新，c[i]+x即可

b[i]=c[i]*(i-1)那么b[i]=(c[i]+x)*(i-1)即b[i]=(c[i])*(i-1)+x*(i-1)我们更新x*(i-1)即可

更新效果：把x位置后面所有的数的值+w

区间更新：

[L,R]+w=update(r,w)-update(l-1,w)

更新效果：把l位置到r位置所有的数的值+w

区间求和：

由上面证明可知:

∑n1a[i]=n∗∑n1c[i]−∑n1b[i]∑1na[i]=n∗∑1nc[i]−∑1nb[i]

和以前一样求和即可，求和式子换成上面那种即可

更新效果：sum(x)=∑x1a[i]