程序設計競賽中線段樹問題的研究

張樂 毛玉萃 侯瑞辰

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

關鍵詞：程序設計;線段樹;實例

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

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

1 背景

大學生程序設計競賽作為業內認可的比賽鼓勵了一批又一批的大學生投入到程序設計之中。數據結構和算法作為比賽考察的重點是很值得研究的。

1.1為什么要參加程序設計競賽

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

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

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

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

1.3研究線段樹問題的意義

線段樹問題在最近幾年的大學生程序設計競賽中的頻繁出現以及之前的比賽中因對于線段樹問題研究的不透徹而與獎牌失之交臂，引起了同學們對線段樹問題的重視[1-3]。

2線段樹的理論分析

2.1 線段樹的作用

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

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

2.2 線段樹的原理

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

2.3 線段樹的函數功能

線段樹至少需要建樹函數，其功能是初始化線段樹，將線段樹的所有節點置為要維護的數組相應區間的初值。

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

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

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

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

3.1 線段樹的節點結構

節點的結構如下：

1）所有子節點即該節點代表區間的最小值。

2）需要區間修改時需要一個懶標記。

C++代碼如圖1所示。

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

3.2 線段樹完成操作所需的函數

3.2.1 建樹

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

其中參數l，r為建立線段樹維護數組的區間，x為當前節點編號。

3.2.2 單點修改

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

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

3.2.3 區間修改

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

其中left，right為要修改的區間，其他與單點修改的含義相同。

3.2.4 單點查詢

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