樹狀陣列小結

前言

1. 在近三周的時間內，我主要復習了線段樹和樹狀陣列，但是線段樹在遇到一道壓位黑題崩掉后就寫不動了，
2. 突發奇想，我決定給這段時間的復習內容寫個總結，本蒟蒻實力有限，如果某些做法比較拉請諒解
3. 本總結默認你已經會樹狀陣列的基本內容，

【壹】單點修改，區間和查詢

1. 最經典的要用樹狀陣列維護的題，( \(P.S.\) 用線段樹也可以，但是常數較大，并且碼量大，不優雅)
2. 屬于樹狀陣列基本內容，在此不多講解，

【貳】區間修改相同值，單點查詢

1. 需要用差分解決，差分后求前綴和得到的就是單點的值，
2. 同時，差分代表的是與前一個的差值，所以我們只需要修改一頭一尾(對于區間 \([a,b]\) ，$ add(a,1),add(b+1,-1) $ )
3. \(O(n)\) 預處理，\(O(m \log n)\) 修改+查詢
4. 線段樹的延遲標記可以達到相同的效率，但如上文所言，不優雅

【叁】區間修改相同值，區間查詢

1. 雖然線段樹碼量大，但是專業的人做專業的事，大部分情況還是讓線段樹來做要好一些(樹狀陣列很難寫)
2. \(But\) 在一些特殊情況，樹狀陣列好用得多，

例題 校門外的樹

• 一道罕見的區間修改區間查詢的樹狀陣列題，
• 因為查詢的是樹的種數，差分是難以解決的，
• 根據題意，可以轉化成這個問題：查詢一個區間與目前存在區間有交集的數目，
• 而這樣對于每個存在的區間分三種情況：左端點在區間內，右端點在區間內，和左右端點都在區間內，但對于第三種情況是比較難解決的，
• 所以我們考慮改下定義：求與詢問區間沒有交集的數目，
• 這樣就非常好解決了，分成兩種情況：左端點在區間右邊和右端點在區間左側，樹狀陣列優化左右端點位置前綴和，
• 但由于是前綴和，左端點在區間右邊又要轉化為總的減去左端點在區間左側和區間內的情況，
• 那答案就是 總-（總-（左端點在區間左側+左端點在區間內）-（右端點在區間左側）= 左端點在查詢區間右端點左側+右端點在查詢區間左端點左側 ，

例題 [SDOI2009] HH的項鏈

• 這道題按照常規思路肯定是在線查詢，但很難維護（至少我沒想出來），
• 但這道題有一個特性：沒有修改操作，
• 那么這道題完全可以離線做（很多題離線可以騙到很多分，這道題更是可以得到全分），
• 我們可以把詢問區間按右端點升序排序，然后每次更新到右端點的每個位置左側的花的種類數，然后進行區間查詢，
• 但花的種類數還是很難維護，原因在于沒法快速判定或在空間允許范圍內區間查詢某個位置和另一個位置上的話是否相同，
• 這就是離線的優越性所在，因為更新到當前詢問的右端點，所以必定是右端點往左延伸的一個區間，那么只要保證每種花最靠右的存在，其它的拔掉，就能保證不重不漏，

【肆】樹狀陣列找逆序對

1. 這也是樹狀陣列的經典用途，也是 \(CDQ\) 分治的必備知識，當然由于范圍問題，大部分時候都得離散化，
2. 這也屬于基礎內容，不再講解，

例題 火柴排隊

• 由于要讓總的平方差最小，肥腸容易想到讓兩堆火柴大小排名相同的作為一對，易證，歡迎各位讀者自己證明，
• 而由于每次只能交換左右兩個，那就類似于冒泡排序，但模擬冒泡排序顯然T掉，
• 而用冒泡排序找的本質便是找逆序對個數，
• 那這道題的思路是先離散化，再按照其中一排火柴的位置順序進行排序（最抽象的地方），最后利用樹狀陣列找逆序對，

小練習 三維偏序(陌上花開)

• 模板，自己去做吧，問就是作者到現在都還沒去做，

【伍】樹狀陣列+二分查找空位

1. 在某些情況下，我們希望能快速找到空位，相比 \(O(n)\) 查找，\(O(\log n^2)\) 看起來要更優秀一點 (\(P.S.\) 如 \(DFS\) 之類的題盡量不要使用，\(DFS\) 由于時間復雜度的問題，資料范圍比較小，樹狀陣列+二分由于常數問題，反而要慢)，
2. 具體做法：

inline int find(int p){//找目前排名p的存在的點
	int l=1;
	int r=n;
	while(l<=r){
		int mid=(l+r)/2;
		if(ask(mid)>=p)r=mid-1;
		else l=mid+1;
	}
	return l;
}

例題 [SHOI2013] 洗牌

• 這道題作為紫題還是有點太水了
• 這道題給的數數量算中等，首先考慮模擬，
• 每次向后跳給定的切牌的數量（切的牌都是牌頂的牌），同時如果超過了n，就再從頭開始跳，不過由于荷官可能會切好完整幅牌很多次，所以要進行取模，減少作業量，

p=(p+r)%(n-i+1)==0?n-i+1:(p+r)%(n-i+1);
\\p表示每一輪取的是牌頂的第幾張，r表示切了幾張牌

小練習 Intervals

• 雙倍經驗
• 這道題做法很多，可以用差分約束，可以用貪心+線段樹，也可以用貪心+樹狀陣列+二分找空位，
• 由于這道題的重心并不是在資料結構維護上，所以不多講解，留作讀者思考，
• \(P.S.\) 這道題也提醒了我們，樹狀陣列只是個資料結構，它是用來輔助的，而不一定是主要的，裸的樹狀陣列花樣肯定沒有在某個地方偷偷塞一個的花樣多，不能因為重點不在資料結構就不去思考用資料結構進行優化，

【陸】二維樹狀陣列

1. 二維樹狀陣列，就是樹狀陣列套樹狀陣列，用于解決二維平面等情況下的單點查詢區間修改，區間修改單點查詢等問題，
2. 一維樹狀陣列轉到二維樹狀陣列和一維陣列轉到二維陣列思路相同，用兩層回圈解決，

	void add(int x,int y,int c){
		for(int i=x;i<=n;i+=i&-i)
        		for(int j=y;j<=m;j+=j&-j)
        			sz[i][j]+=c;
	}
   	int ask(int x,int y){
   		int ans=0;
     	 	for(int i=x;i<=n;i+=i&-i)
     	   		for(int j=y;j<=m;j+=j&-j)
        			sz[i][j]+=c;
        return ans;
   }

小練習 板子1 板子2

3. 但如果二維陣列控制范圍太大，顯然需要離散化，但是即使離散化了，空間也得開點數*點數，所以在有些情況下我們得壓維，（當然，線段樹也能做，叫做掃描線）

例題 [SHOI2007] 園丁的煩惱

1. 這道題開二維陣列是開不下的，只能壓成一維，
2. 由于沒有修改操作（或者說修改操作與詢問操作分離），這道題也可以（只能）強制離線，把一個詢問拆成4個詢問，
3. 顯然，壓成一維時我們只能查找一個維度 \(x\) 上的前綴和，另一個維度 \(y\) 只能被表示出來,而我們需要查找的是一個點在兩個維度上的前綴和，
4. 顯然，我們不希望只有一維時該點還算進了后方位置，那只要還沒建后方的位置不就行了！便先按 \(y\) 維度升序排序，再按 \(x\) 維度升序排序，按順序依次修改，（可以理解為就是掃描線····）
5. 而這道題我們已經離線了，詢問拆成4個后也要一起排序，當然，一定要注意如果詢問和修改的兩個坐標相同，優先修改，

例題 [SDOI2009] 虔誠的墓主人

1. 這道題很有意思，因為它不僅對前綴有要求，還對后綴有要求，

2. 但是如果我們預處理提前記住每一行每一列有多少個數，后綴自然輕松解決，

3. 通過資料范圍能顯然看出得要離散化+壓維（前提是知道用樹狀陣列，逃），

4. 但相信很多同學看到是個空地，心想那么大的地方，樹就幾棵，空地千千萬，這時間不就炸掉了嗎！而且不能離散化！蚌埠住了，

5. 實則忽略了重要限制條件，上下左右都得有 \(k\) 棵常青樹，也就是說，只有空地所在的行和列都得有常青樹才行，

6. 同時由于上下左右可能不止 \(k\) 棵，隨便選就行，顯然組合數 \(\mathrm{C}_n^k\)，

7. 那我們就在掃描的同時計算答案，設目前的種樹的坐標是\((x,y)\) ,上一次種樹的坐標是 \((x,y')\) ，則在\(y'+1 \to y-1\) 范圍內，左右各選 \(k\) 棵的方案數一樣，那我們只需要算出來區間每個位置上下各選 \(k\) 棵樹的方案數，用樹狀陣列維護以便查找區間和，

8. 所以這道題用樹狀陣列維護的內容不再是有上方幾棵樹，而是每個位置的方案樹，每次種樹時進行單點修改方案樹，

【柒】總結

1. 樹狀陣列不屬于不教就不會的型別，大部分變形完全可以在考場上現推出來的，這就需要諸位讀者勤思考，

2. 樹狀陣列大部分都可以用線段樹代替，并且有不少功能只有用線段樹才能實作，這并不意味著樹狀陣列死了，它依然以其優美的實作方式，簡潔的代碼，常數小等優點活躍，

3. 說到底，樹狀陣列也只是一個資料結構，樹狀陣列，線段樹，平衡樹，會敲板子是沒用的，不和其它問題糅到一起，用來優化演算法，它是不完整的，殘缺的，會寫重要，但會做更重要，

\(\cal {Made \ By \ YuGe}\)

標籤：C++

上一篇：在GITHUB上從HTTPS轉移到SSH

下一篇：Git，GitHub。如何找到我一段時間前克隆的確切版本？