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

張樂 毛玉萃 侯瑞辰

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

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

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

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

1.3研究線段樹問題的意義

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

2線段樹的理論分析

2.1 線段樹的作用

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

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

2.2 線段樹的原理

線段樹是一種二叉搜索樹，每個(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)回答詢問時(shí)回答代表相應(yīng)所有區(qū)間的和。當(dāng)修改時(shí)以懶標(biāo)記記錄當(dāng)前節(jié)點(diǎn)的所有子節(jié)點(diǎn)也需要進(jìn)行修改，但是如果不訪問它的子節(jié)點(diǎn)，就不需要將修改落實(shí)到子節(jié)點(diǎn)，所以稱為懶標(biāo)記。如此也保證了修改時(shí)的時(shí)間復(fù)雜度也不會(huì)超過[O（logn）][1，4]。

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

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

如需修改，分為單點(diǎn)修改和區(qū)間修改，當(dāng)只需要單點(diǎn)修改時(shí)無須懶標(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ū)間加，查詢?yōu)閰^(qū)間最小值時(shí)將該節(jié)點(diǎn)代表的子區(qū)間最值直接加上要加的值，并將懶標(biāo)記加上要加的值即可。

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

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

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

3.1 線段樹的節(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ù)組是線段樹本體，對(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ù)

3.2.1 建樹

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

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

3.2.2 單點(diǎn)修改

線段樹單點(diǎn)修改時(shí)無須懶標(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)查詢

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