符智基，趙義霞，劉 利

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

0 引言

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

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

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

1 線段樹的簡介

線段樹是一種用于存放與處理給定區(qū)間信息的數(shù)據(jù)結構，形如一棵二叉樹，每個節(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 四類典型應用場景

在程序設計競賽中，線段樹能與字符串、圖論、計算幾何、動態(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 結束。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 樹形結構信息的維護

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

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

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

圖2 樹形結構舉例圖

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

2.3 帶修改的結合律信息的維護

線段樹常用于維護帶修改的結合律信息，最經(jīng)典的有加減法、乘法、動態(tài)字符串的哈希值等等。這類信息在修改了某個下標的元素后，包含該下標的全部子區(qū)間都會受到影響。每次詢問區(qū)間最優(yōu)解的時間復雜度為O(N)?？梢岳谩熬€段樹節(jié)點中，包含某個下標的區(qū)間節(jié)點個數(shù)最多為個”這一性質，自下往上利用線段樹合并更新，快速算出全局最優(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，得出結果一致，答案為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ī)劃的轉移過程進行優(yōu)化，在程序設計競賽中屢見不鮮。荊慧[8]、鄒玉金[9]也提出了基于線段樹的動態(tài)規(guī)劃優(yōu)化算法，對“最長上升子序列”、“郵局問題”兩類經(jīng)典動態(tài)規(guī)劃問題進行了優(yōu)化。除這兩類問題外，仍存在許多動態(tài)規(guī)劃問題可以使用線段樹進行優(yōu)化，這些問題都具有一個共同點——“其轉移過程中的子問題滿足區(qū)間連續(xù)”。

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

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

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

枚舉反轉區(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 結束語

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