程序設(shè)計競賽中線段樹的四類典型應用場景＊

符智基，趙義霞，劉 利

(惠州學院計算機科學與工程學院，廣東 惠州 516007)

0 引言

高校對學生算法的理解和設(shè)計能力的培養(yǎng)越來越重視。許多程序設(shè)計類競賽中也很重視學生的代碼把控能力和團隊配合能力[1-4]，這類競賽能夠檢測學生算法水平以及學校算法教學成果。“線段樹”作為經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，是程序設(shè)計競賽的高頻考點。

在程序設(shè)計競賽中，線段樹應用場景復雜，靈活多變，不單獨作為模板考察?，F(xiàn)有教材[1-7]闡述了線段樹的基本理論和模板實現(xiàn)，未對其在競賽中的應用場景進行歸類總結(jié)。學生盡管學習了線段樹的基本用法，但在面對競賽題目時仍束手無策。

本文針對以上問題，根據(jù)現(xiàn)有資料進行深入研究，結(jié)合參加ACM 競賽的經(jīng)驗，歸納出了關(guān)于線段樹在程序設(shè)計競賽中的四類典型應用場景。以此幫助學習者建立線段樹在程序設(shè)計競賽中的應用體系，降低學習難度，提升學習效率。

1 線段樹的簡介

線段樹是一種用于存放與處理給定區(qū)間信息的數(shù)據(jù)結(jié)構(gòu)，形如一棵二叉樹，每個節(jié)點代表一段連續(xù)的區(qū)間。可以在單次O(log N)時間復雜度下實現(xiàn)單點修改、單點查詢、區(qū)間修改、區(qū)間查詢。

對于表示區(qū)間[L,R]的節(jié)點，其左兒子代表的區(qū)間為[L,M]，右兒子代表的區(qū)間為[M+1,R]，其中M=。每個節(jié)點往下延申都二分其區(qū)間長度，因此，存儲區(qū)間大小為N的線段樹的深度為，這是線段樹一系列操作時間復雜度為O(log N)的重要前提。存放區(qū)間信息[1,N]的線段樹全部節(jié)點個數(shù)不超過，編程時，使用大小為4×N的數(shù)組存儲，空間復雜度為O(N)。

2 四類典型應用場景

在程序設(shè)計競賽中，線段樹能與字符串、圖論、計算幾何、動態(tài)規(guī)劃等算法混合使用，起到降低原算法時間復雜度的作用。例如：維護動態(tài)字符串的哈希值、優(yōu)化掃描線算法、優(yōu)化建圖等等。其用法各式各樣，靈活多變。下面通過例題分析的形式，對四類典型應用場景進行描述，每類場景均附相同類型的題目推薦。例題的參考代碼可從作者博客（https://blog.csdn.net/m0_68776464?type=blog）獲得。題目的來源網(wǎng)站有POJ（http://poj.org/），HDU（http://acm.hdu.edu.cn/），CF（https://codeforces.com/），洛谷（https://www.luogu.com.cn/）。

2.1 掃描線算法的優(yōu)化

掃描線算法多用于求解二維平面上多個矩形的面積覆蓋和周長問題，維護矩形重疊區(qū)域的信息。矩形個數(shù)為N時，樸素的掃描線算法的時間復雜度為O(N2)，使用線段樹可以將其時間復雜度優(yōu)化至O(N log N)。

例題（POJ1151）：二維平面上N個矩形，每個矩形給出左下角坐標(lx,ly)和右上角坐標(rx,ry)，計算被矩形覆蓋的區(qū)域面積，被多個矩形覆蓋的區(qū)域只計算一次。其中1 ≤N≤105,1 ≤lx

使用一條平行于X軸的掃描線，從下往上掃描。定義一個整型數(shù)組cn t，cn t[i]表示掃描線[i-1,i]處被幾個矩形覆蓋。掃描線遇到矩形平行于X軸的邊時停下計算貢獻，再更新cn t數(shù)組。掃描線兩次停止位置之間的區(qū)域，被矩形覆蓋的面積為“掃描線移動的距離”與“cn t數(shù)組中大于0 的元素個數(shù)”的乘積。圖1所示例子具體過程如下。

圖1 poj1151舉例圖

⑴掃描線在y1 開始，cn t數(shù)組元素全置0。cn t數(shù)組中[x1+1,x3]的值全部要+1。

⑵掃描線在y2 停下。cn t數(shù)組有x3-x1 個大于0 的元素，掃描線移動距離為y2-y1，掃描區(qū)域矩形覆蓋的面積為(x3-x1)×(y2-y1)。cn t數(shù)組中[x2+1,x4]的值全部要+1。

⑶掃描線在y3 停下。cn t數(shù)組有x4-x1 個大于0的元素，掃描線移動距離為y3-y2，掃描區(qū)域矩形覆蓋的面積為(x4-x1)×(y3-y2)。cn t數(shù)組中[x1+1,x3]的值全部要-1。

⑷掃描線在y4 結(jié)束。cn t數(shù)組有(x4-x2)個大于0的元素，掃描線移動距離為y4-y3，掃描區(qū)域矩形覆蓋的面積為(x4-x2)×(y4-y3)。cn t數(shù)組中[x2+1,x4]的值全部要-1。

被矩形覆蓋的區(qū)域總面積等于過程①～④所求面積的總和。將每個矩形區(qū)域(lx,ly,rx,ry)拆分成兩個事件：(ly,lx,rx,1)和(ry,lx,rx,-1)。將全部事件按照y值排序，每個事件對cn t數(shù)組的更新區(qū)域為[lx+1,rx]，是一段連續(xù)的區(qū)間，均為區(qū)間加減。因此可以使用線段樹優(yōu)化，維護cn t數(shù)組中大于0 的元素的個數(shù)，時間復雜度為O(N log N)。需要注意的是，該題矩形坐標范圍較大，需要將坐標值離散化處理。

同場景題目——洛谷P1502、POJ1177、POJ2482、HDU1255、HDU3255、HDU3265。

2.2 樹形結(jié)構(gòu)信息的維護

許多關(guān)于樹形結(jié)構(gòu)的題型，涉及子樹或樹上路徑信息的修改與查詢。類似于這種樹上問題，如果每次操作都逐點遍歷，單次操作的時間復雜度為O(N)。先利用dfs 序、樹鏈剖分等方法將樹結(jié)構(gòu)區(qū)間化，再用線段樹維護，可將單次操作時間復雜度降低至O(log N)。

例題：一棵具有N個節(jié)點的有根樹。Q次操作，操作有兩種：①修改樹上某個節(jié)點的權(quán)值；②查詢樹上某棵子樹全部節(jié)點的權(quán)值和。

如圖2 所示，一棵以節(jié)點1 為根的樹。對該樹dfs遍歷，得到一種可能的入棧順序為[1,7,2,6,4,3,8,5]。可以發(fā)現(xiàn)，以任意節(jié)點為根的子樹，子樹內(nèi)全部節(jié)點都在dfs序列的其中一段連續(xù)區(qū)間（該子樹根節(jié)點入棧和出棧的時間區(qū)間）。利用這個性質(zhì)操作：①轉(zhuǎn)換為線段樹在dfs 序列的單點修改，②轉(zhuǎn)換為線段樹在dfs 序列的區(qū)間查詢。

圖2 樹形結(jié)構(gòu)舉例圖

同場景題目——洛谷P3384、POJ2763、POJ3237、HDU3966、CF343D、CF877E。

2.3 帶修改的結(jié)合律信息的維護

線段樹常用于維護帶修改的結(jié)合律信息，最經(jīng)典的有加減法、乘法、動態(tài)字符串的哈希值等等。這類信息在修改了某個下標的元素后，包含該下標的全部子區(qū)間都會受到影響。每次詢問區(qū)間最優(yōu)解的時間復雜度為O(N)。可以利用“線段樹節(jié)點中，包含某個下標的區(qū)間節(jié)點個數(shù)最多為個”這一性質(zhì)，自下往上利用線段樹合并更新，快速算出全局最優(yōu)解，單次詢問時間復雜度降低為O(log N)。

例題（CF1609E）：一個長度為N且僅由字符'a','b','c'組成的字符串S。Q次操作，每次操作給出一個整數(shù)pos和一個字符ch，表示將字符串中下標（從1 開始）為pos的元素替換為ch。每次操作后，輸出至少需要修改幾個位置的字符，才使得字符串不包含子序列"abc"。其中1 ≤N,Q≤105,1 ≤pos≤N,ch∈['a','b','c']。

每次修改后遍歷字符串判斷是否包含子序列"abc"，時間復雜度為O(N×Q)。

選取任意滿足范圍要求的k，得出結(jié)果一致，答案為min{Cost[1][N][0][t]},(0 ≤t≤2)。

線段樹的節(jié)點[L,R]維護一個4×4 的二維數(shù)組，表示Cost[L][R][][]。修改下標pos，僅需修改線段樹中包含pos的節(jié)點，每個節(jié)點利用左右兒子合并更新，總時間復雜度為O(43×Q×log N)。同場景題目——HDU4578、HDU3973、HDU3308、CF-gym102798G。

2.4 動態(tài)規(guī)劃算法的優(yōu)化

使用線段樹對動態(tài)規(guī)劃的轉(zhuǎn)移過程進行優(yōu)化，在程序設(shè)計競賽中屢見不鮮。荊慧[8]、鄒玉金[9]也提出了基于線段樹的動態(tài)規(guī)劃優(yōu)化算法，對“最長上升子序列”、“郵局問題”兩類經(jīng)典動態(tài)規(guī)劃問題進行了優(yōu)化。除這兩類問題外，仍存在許多動態(tài)規(guī)劃問題可以使用線段樹進行優(yōu)化，這些問題都具有一個共同點——“其轉(zhuǎn)移過程中的子問題滿足區(qū)間連續(xù)”。

例題（原創(chuàng)）：長度為N的整形數(shù)組A（下標從1 開始），遞增度為。選擇一段任意長度的區(qū)間[L,R]反轉(zhuǎn)。例如數(shù)組A=[1,2,3,4,5,6]，反轉(zhuǎn)區(qū)間[2,5]，數(shù)組變成A=[1,5,4,3,2,6]。一次區(qū)間反轉(zhuǎn)后數(shù)組的遞增度最大為多少？其中1 ≤N,Ai≤105。

一個樸素的做法，枚舉全部可能操作的區(qū)間，對于每種操作都遍歷一遍數(shù)組計算遞增度，時間復雜度為O(N3)。

優(yōu)化遍歷計算遞增度這一過程，定義兩個整型數(shù)組sum和rev。其中sum[i]表示子數(shù)組[1,i]的遞增度，rev[i]表示子數(shù)組[i,N]反轉(zhuǎn)后的遞增度。枚舉反轉(zhuǎn)區(qū)間[L,R]，反轉(zhuǎn)后的數(shù)組的遞增度可以O(shè)(1)計算，時間復雜度為O(N2)。公式如下：

枚舉反轉(zhuǎn)區(qū)間[L,R]的右端點R，令X=sum[N]-sum[R+1]-rev[R]，對于左端點L，令Y=sum[L-1]+rev[L]。有以下幾種情況。

①1≤AL-1

②1 ≤AL-1

③AL-1≥AR，1 ≤AL

④AL-1≥AR，AL≥AR+1。答案為X+Y。

X為定值，Y越大越好。每種情況有兩種限制，可以視作在二維平面中，給出左下角和右上角坐標的矩形區(qū)域內(nèi)的最大Y值。每次遍歷到下標R，用sum[R-1]+rev[R]來更新坐標(AR-1,AR)，維護最大值。二維平面上矩形區(qū)域的最值查詢，單點修改，可以使用線段樹套線段樹進行求解?？臻g復雜度為O(N×log2N)，時間復雜度為O(4×N×log2N)。

同場景題目——HDU3016、HDU3607、HDU6447、POJ1769、POJ3171、CF833B。

3 結(jié)束語

為了降低線段樹的學習難度，本文通過例題，分析、總結(jié)并闡述了“掃描線算法的優(yōu)化”、“樹形結(jié)構(gòu)信息的維護”、“帶修改的結(jié)合律信息的維護”和“動態(tài)規(guī)劃算法的優(yōu)化”四類線段樹的典型應用場景。隨著信息技術(shù)的發(fā)展，近年來提出關(guān)于線段樹在程序設(shè)計競賽中的新用法，如區(qū)間最值操作與歷史最值問題、李超線段樹等。由于篇幅有限，本文未對其進行討論。這類線段樹的新用法難度較高，本文線段樹在程序設(shè)計競賽中的典型應用，可以為學習者建立系統(tǒng)性的認識，為更高難度的應用研究奠定基礎(chǔ)。