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

符智基，趙義霞，劉 利

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

0 引言

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

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

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

1 線段樹的簡介

線段樹是一種用于存放與處理給定區間信息的數據結構，形如一棵二叉樹，每個節點代表一段連續的區間?？梢栽趩未蜲(log N)時間復雜度下實現單點修改、單點查詢、區間修改、區間查詢。

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

2 四類典型應用場景

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

2.1 掃描線算法的優化

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

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

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

圖1 poj1151舉例圖

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

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

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

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

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

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

2.2 樹形結構信息的維護

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

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

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

圖2 樹形結構舉例圖

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

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

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

例題（CF1609E）：一個長度為N且僅由字符'a','b','c'組成的字符串S。Q次操作，每次操作給出一個整數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)。

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

2.4 動態規劃算法的優化

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

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

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

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

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

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

3 結束語

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