數組小技巧 區間操作

猛然發現自己的個人主頁被訪問了1,000次以上了！

嘛嘛，那麼講一些自己的關於數組的心得體會吧。正好也是整理一下。

聲明：

查詢單個元素：給定一個下標，獲取數組上對應下標上元素的值

修改單個元素：給定一個下標，讓對應下標上的元素加上一個給定的值

查詢區間和：對於一個給定的合法區間[i,j]來說，查詢數組在[i,j]上的所有元素之和

修改區間和：對於一個給定的合法區間[i,j]來說，讓[i,j]里的每一個元素都加上某一個給定的值

單個元素雖然可以看成對於某個區間[i,i]上的操作，但是我還是要特意拿出來。

數組下標從1開始

普通數組：

const int maxm=100;int arr[maxm];

查詢單個元素時間複雜度: O(1)

修改單個元素時間複雜度: O(1)

查詢區間和時間複雜度: O(n)

修改區間和時間複雜度: O(n)

評價：被廣泛使用的結構......

前綴和：

int sum[maxm];for(int i=1;i<maxm;++i)sum[i]=sum[i-1]+arr[i];

即對於前綴和數組sum來說

sum[i]=arr[1]+arr[2]+......+arr[i]

查詢單個元素時間複雜度: O(1) -> sum[i]-sum[i-1]

修改單個元素時間複雜度: O(n)

查詢區間和時間複雜度: O(1) -> sum[j]-sum[i-1]

修改區間和時間複雜度: O(n)

評價：在數組不會發生變化，且需要頻繁查詢區間和的時候的很好的選擇。

差分：

int diff[maxm]diff[1]=arr[1];for(int i=2;i<maxm;++i)diff[i]=arr[i]-arr[i-1];

即對於差分數組diff來說：

diff[1]=arr[1], diff[i]=arr[i]-arr[i-1];

查詢單個元素時間複雜度: O(n) -> diff[i]+diff[i-1]+.... + diff[1]

修改單個元素時間複雜度: O(1) -> 只考慮涉及到arr[i]的元素即可

查詢區間和時間複雜度: O(n)

修改區間和時間複雜度: O(1) -> 考慮[i,j]區間+1，則diff[i]+=1,diff[j+1]-=1即可

評價：好像用得不是很多...用在需要對區間進行更新而且中間還不能查詢的時候。

三者關係：

普通數組求前綴和變為前綴和數組

差分數組求前綴和變為普通數組

前綴和數組差分變為普通數組

普通數組差分變為差分數組

引入數據結構：樹狀數組，此處不對樹狀數組原理做任何解釋

//定義操作lowerbit//bit->binary index treeinline int lowerbit(int x){return x&-x;}//定義插入操作int _ins(int i,int x){while(i<maxm)bit[i]+=x,i+=lowerbit(i);}//定義查詢操作int query(int i){ int ans=0; while(i)ans+=bit[i],i-=lowerbit(i); return ans;}for(int i=1;i<maxm;++i)_ins(i,arr[i]);

以上是最基本的樹狀數組代碼，即對原arr數組建立一個樹狀數組

查詢單個元素時間複雜度: O(lgn)

修改單個元素時間複雜度: O(lgn)

查詢區間和時間複雜度: O(lgn) -> query(j)-query(i-1)

修改區間和時間複雜度: O(nlgn)

讓我們考慮對差分數組diff建立樹狀數組：

for(int i=1;i<maxm;++i)_ins(i,diff[i]);

這樣做完之後我們就能得到：

查詢單個元素時間複雜度: O(lgn)

修改單個元素時間複雜度: O(lgn)

查詢區間和時間複雜度: O(nlgn)

修改區間和時間複雜度: O(lgn) -> 考慮區間[i,j]+1，_ins(i,1), _ins(j+1,-1)

問題來了，樹狀數組和對diff建立的樹狀數組都不能很好的進行區間修改和查詢......那麼我們有沒有什麼辦法呢

考慮 arr[1]+arr[2]+....+arr[n]

用diff改寫一下成為

(diff[1]) + (diff[1] + diff[2]) + ..... + (diff[1] + diff[2] + ..... + diff[n])

合併一下同類項

n*diff[1] + (n-1)*diff[2] + ...... + 1*diff[n] ---- (1)

改寫一下式子

n*(diff[1] + diff[2] + ...... + diff[n]) - ( 0*diff[1] + 1*diff[2] + ...... + (n-1)*diff[n]) ---- (2)

至此，我們便得到了可以進行區間修改的差分樹狀數組了。

我們我們不僅對差分數組diff建立一個樹狀數組快速求diff上的區間和，同時對 (i-1)*diff[i] 也建立一個樹狀數組快速求該數組的區間和，再相減即可。

//(i-1)*diff[i]數組的ins和query//[i,j]+val時_ins(i,(i-1)*val);_ins(j+1,-(n-j-1)*val);//查詢[i,j]時query(j)-query(i-1);

至此，我們通過建立兩個樹狀數組即可得到區間修改和區間查詢的良好數據結構了。

查詢單個元素時間複雜度: O(lgn)

修改單個元素時間複雜度: O(lgn)

查詢區間和時間複雜度: O(lgn)

修改區間和時間複雜度: O(lgn)

評價：常數也線段樹要小，支持區間修改的結構。可是我沒怎麼用過，一般都是寫打lazy tag的線段樹了。

思考題：

在上一段中，我們是對(2)式建立了兩個樹狀數組來完成區間操作，那麼，我們能不能僅僅對(1)式建立一個樹狀數組來完成區間操作，而且還要少一倍的空間呢？

推薦閱讀：