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

張樂 毛玉萃 侯瑞辰

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

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

中圖分類號：TP311.52? ? ? 文獻標識碼：A

文章編號：1009-3044（2021）25-0160-05

1 背景

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

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

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

1.2為什么需要研究線段樹問題

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

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

1.3研究線段樹問題的意義

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

2線段樹的理論分析

2.1 線段樹的作用

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

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

2.2 線段樹的原理

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

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

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

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

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

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

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

3.1 線段樹的節(jié)點結(jié)構(gòu)

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

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

2）需要區(qū)間修改時需要一個懶標記。

C++代碼如圖1所示。

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

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

3.2.1 建樹

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

其中參數(shù)l，r為建立線段樹維護數(shù)組的區(qū)間，x為當前節(jié)點編號。

3.2.2 單點修改

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

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

3.2.3 區(qū)間修改

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

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

3.2.4 單點查詢

單點查詢時需要先將標記下放，因為懶標記只是暫時不將修改落實到子節(jié)點，但查詢實際值時就需要將修改實際落實到要查詢的節(jié)點。C++代碼如圖5所示。