程序設(shè)計(jì)競(jìng)賽中線段樹(shù)問(wèn)題的研究

張樂(lè) 毛玉萃 侯瑞辰

摘要：介紹了程序設(shè)計(jì)競(jìng)賽中線段樹(shù)的重要性;概括了線段樹(shù)的作用、原理，較詳細(xì)地介紹了相關(guān)的函數(shù)——建樹(shù)、修改和查找;以例題方式介紹了線段樹(shù)的應(yīng)用;最后進(jìn)行了總結(jié)。

關(guān)鍵詞：程序設(shè)計(jì);線段樹(shù);實(shí)例

中圖分類(lèi)號(hào)：TP311.52? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2021）25-0160-05

1 背景

大學(xué)生程序設(shè)計(jì)競(jìng)賽作為業(yè)內(nèi)認(rèn)可的比賽鼓勵(lì)了一批又一批的大學(xué)生投入到程序設(shè)計(jì)之中。數(shù)據(jù)結(jié)構(gòu)和算法作為比賽考察的重點(diǎn)是很值得研究的。

1.1為什么要參加程序設(shè)計(jì)競(jìng)賽

程序設(shè)計(jì)競(jìng)賽可以提高一個(gè)軟件工程師的綜合水平，提升基本的代碼能力以及其對(duì)細(xì)節(jié)的把握能力，能增強(qiáng)人的團(tuán)隊(duì)合作、思維水平和毅力[1-2]。

1.2為什么需要研究線段樹(shù)問(wèn)題

線段樹(shù)是一種樹(shù)形數(shù)據(jù)結(jié)構(gòu)，是一種二叉搜索樹(shù)。二叉搜索樹(shù)一般用于數(shù)據(jù)庫(kù)系統(tǒng)和文件系統(tǒng)，被用于進(jìn)行高效率的排序與檢索操作。而線段樹(shù)不僅有較高效率的排序和檢索操作的功能，還可以高效的計(jì)算某段區(qū)間和修改功能[1-3]。

研究線段樹(shù)問(wèn)題可以用來(lái)解決程序設(shè)計(jì)競(jìng)賽中的一些相關(guān)問(wèn)題，總結(jié)線段樹(shù)的使用方法及范圍。熟悉常見(jiàn)的線段樹(shù)處理問(wèn)題及其解法，盡多掌握程序設(shè)計(jì)類(lèi)競(jìng)賽中的典型線段樹(shù)問(wèn)題，以利于在比賽中取得成績(jī)[1-3]。

1.3研究線段樹(shù)問(wèn)題的意義

線段樹(shù)問(wèn)題在最近幾年的大學(xué)生程序設(shè)計(jì)競(jìng)賽中的頻繁出現(xiàn)以及之前的比賽中因?qū)τ诰€段樹(shù)問(wèn)題研究的不透徹而與獎(jiǎng)牌失之交臂，引起了同學(xué)們對(duì)線段樹(shù)問(wèn)題的重視[1-3]。

2線段樹(shù)的理論分析

2.1 線段樹(shù)的作用

當(dāng)需要維護(hù)一個(gè)數(shù)組時(shí)，需要多次查詢(xún)區(qū)間有結(jié)合性的運(yùn)算區(qū)間的運(yùn)算結(jié)果（如區(qū)間最值，加和，乘積，異或等）并進(jìn)行有結(jié)合性的修改操作（區(qū)間加，區(qū)間乘，區(qū)間異或）時(shí)，若數(shù)組的長(zhǎng)度達(dá)到10000以上的量級(jí)，查詢(xún)修改也達(dá)到10000以上的量級(jí)時(shí)，n表示數(shù)組大小，m表示操作次數(shù)，樸素的時(shí)間復(fù)雜度為[O（nm）]，直接進(jìn)行修改和查詢(xún)?cè)跀?shù)據(jù)極端時(shí)（如查詢(xún)和修改10000次區(qū)間[1，10000]），循環(huán)遍歷次數(shù)已經(jīng)達(dá)到了億級(jí)，對(duì)于1s的限時(shí)已經(jīng)很難通過(guò)。而一般需要線段樹(shù)的題目數(shù)據(jù)范圍大都是100000的級(jí)別，并且會(huì)包括極端的樣例卡掉樸素方法，所以就需要復(fù)雜度更低的算法。分塊算法雖然也可以通過(guò)100000級(jí)，但在數(shù)字更大時(shí)，分塊算法的[O（msqrtn）]在常數(shù)稍大時(shí)就已無(wú)法通過(guò)。因此就需要復(fù)雜度在[O（mlogn）]及以下的方法[1，4]。

線段樹(shù)可以在[Ologn]復(fù)雜度內(nèi)完成單次區(qū)間修改和查詢(xún)操作，這樣總的時(shí)間復(fù)雜度就是[O（logn）]了。

2.2 線段樹(shù)的原理

線段樹(shù)是一種二叉搜索樹(shù)，每個(gè)節(jié)點(diǎn)代表一個(gè)區(qū)間，其中根節(jié)點(diǎn)代表要維護(hù)的整個(gè)數(shù)組區(qū)間，其它節(jié)點(diǎn)都代表父節(jié)點(diǎn)的區(qū)間的一半，從而保證深度為，每個(gè)節(jié)點(diǎn)儲(chǔ)存了區(qū)間的和（該區(qū)間的和為需要維護(hù)的結(jié)合性操作），當(dāng)回答詢(xún)問(wèn)時(shí)回答代表相應(yīng)所有區(qū)間的和。當(dāng)修改時(shí)以懶標(biāo)記記錄當(dāng)前節(jié)點(diǎn)的所有子節(jié)點(diǎn)也需要進(jìn)行修改，但是如果不訪問(wèn)它的子節(jié)點(diǎn)，就不需要將修改落實(shí)到子節(jié)點(diǎn)，所以稱(chēng)為懶標(biāo)記。如此也保證了修改時(shí)的時(shí)間復(fù)雜度也不會(huì)超過(guò)[O（logn）][1，4]。

2.3 線段樹(shù)的函數(shù)功能

線段樹(shù)至少需要建樹(shù)函數(shù)，其功能是初始化線段樹(shù)，將線段樹(shù)的所有節(jié)點(diǎn)置為要維護(hù)的數(shù)組相應(yīng)區(qū)間的初值。

如需修改，分為單點(diǎn)修改和區(qū)間修改，當(dāng)只需要單點(diǎn)修改時(shí)無(wú)須懶標(biāo)記，只需遍歷到相應(yīng)的葉子節(jié)點(diǎn)并修改其值即可;而當(dāng)需要區(qū)間修改時(shí)，當(dāng)前遍歷到的節(jié)點(diǎn)被包含在要修改的區(qū)間中的時(shí)候，只需修改該節(jié)點(diǎn)的值并相應(yīng)修改其懶標(biāo)記。如修改為區(qū)間加，查詢(xún)?yōu)閰^(qū)間最小值時(shí)將該節(jié)點(diǎn)代表的子區(qū)間最值直接加上要加的值，并將懶標(biāo)記加上要加的值即可。

如需查詢(xún)，分為單點(diǎn)查詢(xún)和區(qū)間查詢(xún)，當(dāng)前節(jié)點(diǎn)被包含在要查詢(xún)的區(qū)間中時(shí)直接返回該節(jié)點(diǎn)中記錄的代表子區(qū)間的和即可。

線段樹(shù)可以維護(hù)具有結(jié)合性的運(yùn)算，下文查詢(xún)以求最小值，修改操作為區(qū)間加為例。

3 線段樹(shù)的函數(shù)分析[1，4-5]

3.1 線段樹(shù)的節(jié)點(diǎn)結(jié)構(gòu)

節(jié)點(diǎn)的結(jié)構(gòu)如下：

1）所有子節(jié)點(diǎn)即該節(jié)點(diǎn)代表區(qū)間的最小值。

2）需要區(qū)間修改時(shí)需要一個(gè)懶標(biāo)記。

C++代碼如圖1所示。

tr數(shù)組是線段樹(shù)本體，對(duì)于下標(biāo)為x的節(jié)點(diǎn)，它的左子節(jié)點(diǎn)下標(biāo)為x*2，右子節(jié)點(diǎn)下標(biāo)為x*2+1。

3.2 線段樹(shù)完成操作所需的函數(shù)

3.2.1 建樹(shù)

線段樹(shù)遞歸的去建立節(jié)點(diǎn)，對(duì)于每個(gè)節(jié)點(diǎn)，它代表的區(qū)間總是它父節(jié)點(diǎn)代表的區(qū)間的一半，根節(jié)點(diǎn)代表的區(qū)間為維護(hù)的數(shù)組的大小。C++代碼如圖2所示。

其中參數(shù)l，r為建立線段樹(shù)維護(hù)數(shù)組的區(qū)間，x為當(dāng)前節(jié)點(diǎn)編號(hào)。

3.2.2 單點(diǎn)修改

線段樹(shù)單點(diǎn)修改時(shí)無(wú)須懶標(biāo)記，只需修改要修改的下標(biāo)對(duì)應(yīng)節(jié)點(diǎn)的值并在回溯時(shí)修改父節(jié)點(diǎn)即可。這里還涉及懶標(biāo)記的下放，必須先下放懶標(biāo)記再遞歸。C++代碼如圖3所示。

參數(shù)中p是要修改的下標(biāo)，l、r是當(dāng)前節(jié)點(diǎn)代表的區(qū)間，k是要在區(qū)間上加的量，x是當(dāng)前節(jié)點(diǎn)的編號(hào)。

3.2.3 區(qū)間修改

區(qū)間修改時(shí)只需修改要修改的區(qū)間的父節(jié)點(diǎn)，將修改記錄在懶標(biāo)記上即可。這里的父節(jié)點(diǎn)是必須完全包含在要修改區(qū)間內(nèi)的。同樣需要下放懶標(biāo)記。C++代碼如圖4所示。

其中l(wèi)eft，right為要修改的區(qū)間，其他與單點(diǎn)修改的含義相同。

3.2.4 單點(diǎn)查詢(xún)

單點(diǎn)查詢(xún)時(shí)需要先將標(biāo)記下放，因?yàn)閼袠?biāo)記只是暫時(shí)不將修改落實(shí)到子節(jié)點(diǎn)，但查詢(xún)實(shí)際值時(shí)就需要將修改實(shí)際落實(shí)到要查詢(xún)的節(jié)點(diǎn)。C++代碼如圖5所示。