符智基，趙義霞，劉 利

(惠州學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院，廣東 惠州 516007)

0 引言

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

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

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

1 線段樹的簡介

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

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

2 四類典型應(yīng)用場景

在程序設(shè)計(jì)競賽中，線段樹能與字符串、圖論、計(jì)算幾何、動(dòng)態(tài)規(guī)劃等算法混合使用，起到降低原算法時(shí)間復(fù)雜度的作用。例如：維護(hù)動(dòng)態(tài)字符串的哈希值、優(yōu)化掃描線算法、優(yōu)化建圖等等。其用法各式各樣，靈活多變。下面通過例題分析的形式，對(duì)四類典型應(yīng)用場景進(jìn)行描述，每類場景均附相同類型的題目推薦。例題的參考代碼可從作者博客（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)化

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

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

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

圖1 poj1151舉例圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

例題（原創(chuàng)）：長度為N的整形數(shù)組A（下標(biāo)從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。

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

優(yōu)化遍歷計(jì)算遞增度這一過程，定義兩個(gè)整型數(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)計(jì)算，時(shí)間復(fù)雜度為O(N2)。公式如下：

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

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

3 結(jié)束語

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