【算法思想篇】樹狀數組區間修改，區間查詢

樹狀數組進階：

區間修改與區間查詢

今天老糊塗了，樹狀數組忘記了，基本的隻要單點修改+區間查詢功能，如果要進行區間加操作，需要把樹狀數組進行改造。

我們首先來回顧樹狀數組的功能：

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]