當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

什么是线段树？

發布時間：2024/4/11 编程问答 31 豆豆

生活随笔收集整理的這篇文章主要介紹了什么是线段树？小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

什么是線段樹？

文章目錄

什么是線段樹？
- 一、簡介
- 二、線段樹的結構與建樹
- - 如何存儲這個線段樹呢?
- 三、區間查詢
- - 那么如何判斷兩個區間是否有交集？
- 四、單點修改
- 五、區間修改、懶標記
- - 懶標記
- 六、完整代碼
- - 線段樹節點的構造
  - 下傳標記的函數
  - 區間修改的函數
  - 加入懶標記后的建樹函數
  - 加入懶標記后的查詢函數
  - 主函數中的調用
- 七、區間合并操作與懶標記的運用
- 八、權值線段樹
- - 動態開點
- 九、查找排名第k的數
- 十、查詢數 k 的排名

一、簡介

線段樹是在算法競賽中常用來維護區間信息的數據結構，同時，線段樹的理解難度較樹狀數組低（當然是在理解遞歸的前提下）。
線段樹可以在 $O (l o g N)$ 的時間復雜度內實現對數組的單點修改、區間修改、區間查詢等操作。
下面以一個簡單的例題進行介紹：
給定一個數組 arr[0 … n-1]，執行不超過10萬次以下兩個操作：
1、輸出數組中 [left, right] 區間內的數的和，也就是 a[left] + a[left+1] + … + a[right]
2、將數組 [left, right] 區間內的所有數更改為 k。

二、線段樹的結構與建樹

線段樹將每個長度不為1的區間劃分為左右兩個區間，并遞歸處理，通過合并左右兩個區間的信息來求得該區間的信息。
對于例題來說，我們想要得到的是指定區間里數的和，那么，我們要求的區間信息便是該區間數的和，合并左右兩個區間的信息即是將兩個區間的值進行相加。
例如對于數組 arr = [ 13 , 99 , 23 , 66 , 7 , 2 , 56 , 45 ] 而言：
數組長度為 8，以中點為分界點，劃分為左右子區間：

設 mid = (left + right) / 2 ，則 [left, mid] 為左子區間，[mid + 1 , right] 為右子區間（如果區間長度是奇數，則左子區間比右子區間大1）；接著，對子區間遞歸劃分，直到區間長度為 1。
我們對數組 arr = [ 13, 99, 23 , 66 , 7 , 2 , 56 , 45 ] 執行上面提到的遞歸劃分過程后：

在回溯的過程中，合并子區間的信息，即將子節點的值加起來：

此時一顆線段樹其實就已經建成了，你可以將你的手機上下顛倒看一看這個圖。
線段樹的結構如下：

如何存儲這個線段樹呢?

最簡單的方法是堆式建樹
即像下面這樣，我們可以用一個數組直接存儲線段樹的節點，節點在數組中下標如圖：

由圖，我們可以發現一個規律：
對于一個節點，設其在數組中下標為 $p$ ，則該節點的左子節點的下標為 $2 ? p$ ，右子節點的下標為 $2 ? p + 1$ ，父節點的下標為 $p / 2$ (取下界)。
建樹的代碼：

int arr[100010];//原數組 int tree[400010]; //線段樹數組//建立線段樹，[l, r]為節點代表的范圍， p 為節點在線段樹數組的下標 void build(int left, int right, int p = 1) {//區間長度為 1，節點值即為原數組對應位置的值；if(left == right){tree[p] = arr[left];return;}int mid = (left + right)/2;build(left, mid, 2 * p); //遞歸處理左子區間build(mid + right, right, 2 * p + 1); //遞歸處理右子區間tree[p] = tree[2 * p] + tree[2 * p + 1]; // 合并左右子區間的信息 }

這里有一點需要注意：堆式建樹的線段樹的數組大小需要設為原數組大小的4倍

三、區間查詢

回到例題，建好樹后，如何查詢 [left, right] 區間內數的和？
只需要在線段樹中找到一些節點，這些節點剛好能組成查詢的區間，再合并這些節點的信息即可
這里先放4張圖，看一下查詢過程以及我們需要查詢的節點。
查詢區間 [1, 5] :
查詢區間的數的和即是 $201 + 7 = 208$ .
查詢區間 [3, 6]：
查詢區間的數的和即是 $89 + 9 = 98$
查詢區間 [5, 6] :
查詢區間的數的和即是 $9$
查詢區間 [1, 7] :
查詢區間的數的和即是 $201 + 9 + 56 = 266$
由圖可以看出，在線段樹中查詢指定的區間，其實就是找到一些節點（也就是圖中的粉紅色節點），使這些節點恰好能組成查詢的區間。
顯然，查詢操作所遍歷的節點數（淺藍色節點+粉紅色節點）與樹高成正比，即查詢操作的時間復雜度為 $O (l o g N)$ .
為了查找這些淺藍色節點，從根向下遍歷，每遇到一個節點，可分為2種情況
1、當前節點代表的區間是詢問區間的子集。

例如：詢問區間為 [1, 7] ，當前節點代表的區間為 [1, 4] （大圓圈起部分）是詢問區間的子集，則直接將此節點的值返回即可
區間[5, 6] 和 [7] 也是一樣。
可以發現，情況1的節點即是圖中的粉紅色節點。

2、除第一種情況外，判斷詢問節點與子區間是否有交集，若有，則遞歸處理。

例如：詢問區間為 [1, 7] ，當前節點代表區間為 [1, 8] （大圓圈起部分）與詢問區間有交集，則遞歸處理其左右孩子。
左子區間為 [1, 4] ，是詢問區間 [1,7] 的子集，所以將其返回 sum = 201；
右子區間為 [5, 8] ，與詢問區間 [1,7] 有交集，遞歸調用其左右子節點；
[5,8] 的左子區間 [5,6] ，是詢問區間 [1,7] 的子集，所以將其返回 sum = 201 + 9 = 210;
[5,8] 的右子區間 [7,8] ，與詢問區間 [1,7] 有交集，遞歸調用其左右子節點；
[7,8] 的左子區間 [7] ，是詢問區間的子集，所以將其直接返回 sum = 210 + 56 = 276；
[7,8] 的右子區間 [8] ，與詢問區間不存在子集也不存在交集，回溯到根結點結束。
情況2其實就是圖中淺藍色節點，遞歸完成后合并信息并返回。

那么如何判斷兩個區間是否有交集？

如果詢問區間的左端點小于等于當前節點區間的分界點，則為左子區間相交。

比如當前結點區間為 [1,8]，其分界點為 mid = (1+8)/2=4 ，查詢區間為 [1,7] ，查詢區間的左端點為 1 ，由于 1 < 4 ，所以查詢區間與當前結點區間為左子區間相交。
如果詢問區間的右端點大于當前節點區間的分界點，則與右子區間相交。

比如當前結點區間為 [1,8]，其分界點為 mid = (1+8)/2=4 ，查詢區間為 [5,6] ，查詢區間的右端點為 6 ，由于 6 > 4 ，所以查詢區間與當前結點區間為右子區間相交。
只看兩種情況的描述有點抽象，直接看整體的代碼：

//[nl, nr]為所訪問區間，[l, r]為當前結點代表的區間 int query(int nl, int nr, int l, int r, int p = 1) {//代表當前節點代表的區間為查詢區間的子集if(nl <= l && r <= nr){return tree[p];}//當前區間的分界點int mid = (l + r) / 2;//返回結果int sum = 0;//如果訪問區間的左邊界小于當前節點代表的區間的分界//說明訪問區間和當前節點的左區間相交if(l <= mid){sum += query(nl, nr, l, mid, 2 * p);}//說明訪問區間和當前節點的右區間相交if(r > mid){sum += query(nl, nr, mid+1, r, 2 * p + 1);}//返回結果return sum; }

四、單點修改

看完前兩個步驟的代碼，相信已經發現了：線段樹的一系列操作就是通過遞歸不斷縮小區間，直到找到所需的節點。
那么單點修改的操作就很明顯了：找到對應的區間并修改，回溯時對沿途的節點更新

我們以將數組 arr[4] 的值 66 修改為 8 進行說明，其中 "遞歸" 遞的過程就是找到從根節點 [1,8] 到要修改的結點的 [4] 的路徑，而歸的過程就是對路徑上結點值的修改過程。
修改結點 [4] 的值為 8 ：

修改結點 [4] 的父結點 [3,4] 的值為當前 [3] 的值 23 加上 [4] 的值 8 ，即 23 + 8 = 31 ：
修改節點 [3,4] 的父結點 [1,4] 的值為當前 [3,4] 節點的值 31 和其兄弟節點[1,2] 的值 112 的和，即 112 + 31 = 143：

最后將根節點 [1,8] 的值修改為當前結點 [1,4] 及其兄弟結點 [5,8] 的和，即 143 + 110 = 253:

實現代碼超級簡單（這就是遞歸的魅力，代碼簡潔）：

// 將arr[idx] 的值修改為 k, [l, r] 為當前結點代表的區間 void change_s(int idx, int k, int l, int r, int p = 1) {//代表找到idx的節點if(l == idx && r == idx){tree[p] = k;return;}int mid = (l + r)/2;//遞歸查找左區間if(idx <= mid){change_s(idx, k, l, mid, 2 * p);}//遞歸查找右區間else{change_s(idx, k, mid + 1, r, 2 * p + 1);}//向上更新父親節點tree[p] = tree[2 * p] + tree[2 * p + 1]; }

單點修改的時間復雜度也為 $O (l o g N)$

五、區間修改、懶標記

接下來是線段樹的重頭戲：區間修改。顯然，不可能通過一個個的單點修改來實現區間修改，這樣時間效率還不如直接暴力修改。
區間修改的操作與之前的區間查詢很相似，都是找到若干的區間能組成尋找區間

這里先引入一個新的概念：

懶標記

直接看栗子，我們現在想把數組中 [1,4] 中所有的數修改為 16
那么，我們通過遞歸找到了需要的節點（下圖粉紅色帶圓圈的節點）

這時，我們知道，這個節點的值應該被修改為 64 （16*4=64）（16乘區間長度）。
這時，我們不需要繼續往下遞歸，而是給這個節點打上一個標記。我們可以把這個標記設為16，意為這個區間的數已經被修改為16，如圖所示：

然后回溯的過程中再更新結點的值：
從作用可以體會到為什么叫懶標記（就像別人給你家長一些錢說是給你和弟弟的壓歲錢，然后家長就說先不給你們，等需要用的時候再給你們）
現在，我們再進行下一次修改，要將 [3, 8] 區間內的數修改為 7：
還是一樣的操作，先找到需要的節點，但是，我們在找所需節點時遇到了帶標記的節點（剛剛的區間修改操作打的標記），這時，我們把標記下傳：

下傳完畢后，繼續查找，訪問節點 [3,4] :
找到這些節點后，也是像剛剛一樣，修改節點的值，并打標記。
注意：這里代表區間 [3,4] 的節點原來標記為 16 ，意為該區間已經被修改為16，現在我們想把這個區間更改為7，直接將標記修改即可。
我們想將 [3, 8] 區間內的數修改為 7 :
[3,4] 區間長度為2，所以節點值應改為 7 * 2 = 14，標記為 7；
[5,8] 區間長度為4，所以節點值應改為 7 * 4 = 28，標記為 7；
別忘記回溯時修改沿途節點：
在這里我猜可能有人會有疑惑：為什么加了標記以后就能保證區間修改時間復雜度為 $O (l o g N)$ .
其實很簡單：很顯然區間修改時遍歷過的節點數（淺藍色+粉紅色）與區間查詢時遍歷的節點是一樣的；那么，只有這個節點需要下傳標記，所以區間修改時間復雜度為 $O (l o g N)$ .
代碼如下，當然，加入了懶標記后，之前說到的幾個操作都有少許的變動，這里先給出區間修改的代碼再將全部操作代碼一起給出:

六、完整代碼

線段樹節點的構造

struct seg {int val, tag;bool have_tag; }tree[400010]; //線段樹數組int arr[100010]; // 原數組

下傳標記的函數

void push_tag_down(int p, int l, int r) {//如果當前結點的標記不為 0 ，將當前結點的標記下傳if(tree[p].hava_tag){ int mid = (l + r) / 2;seg root = tree[p], ls = tree[2 * p], rs = tree[2 * p + 1];//結點值為標記值 * 區間長度ls.val = root.tag * (mid -l + 1);ls.tag = root.tag, ls.have_tag = true;rs.val = root.tag * (r - mid);rs.tag = root.tag, rs.hava_tag = true;root.hava_tag = false;} }

區間修改的函數

// k為區間[l, r]內每個數的變化量 void change(int nl, int nr, int k, int l, int r, int p = 1) {// 當該節點的區間是訪問區間的子集if(nl <=l && r <= nr){ tree[p].val = (r - l + 1) * k;tree[p].tag = k;tree[p].hava_tag = true;return;}push_tag_down(p, l, r); //訪問到帶標記的結點就下傳標記int mid = (l + r) / 2;if(nl <= mid) // 與左子區間相交{change(nl, nr, k, l, mid, 2 * p);}if(nr > mid){change(nl, nr, k, mid + 1, r, 2 * p + 1);}tree[p].val = tree[2 * p].val + tree[2 * p + 1].val;//回溯時更新 }

加入懶標記后的建樹函數

//建立線段樹，[l, r]為節點代表的范圍 p 為節點在線段樹數組下標 void build(int l, int r, int p = 1) {tree[p].tag = 0;tree[p].hava_tag = false;if(l == r){tree[p].val = arr[l];return;}int mid = (l - r)/2 ;build(l, mid, 2 * p); // 遞歸處理左子區間build(mid + 1, r, 2 * p + 1); //遞歸處理右子區間tree[p].val = tree[2 * p].val + tree[2 * p + 1].val; //合并左右子區間的信息 }

加入懶標記后的查詢函數

注意，查詢函數中同樣需要下放標記！

//[nl, nr]為所訪問區間， [l, r]為當前節點代表的區間 int query(int nl, int nr, int l, int r, int p = 1) {if(nl <= l && r <= nr) // 當該節點的區間是訪問區間的子集{return tree[p].val;}push_tag_down(p, l, r); // 訪問到就下傳標記int mid = (l + r) / 2;int sum = 0;if(l <= mid) //與左子區間相交{sum += query(nl, nr, l, mid, 2 * p);}if(r > mid) // 與右子區間相交{sum += query(nl, nr, mid + 1, r, 2 * p + 1);}return sum; }

注：這里沒有單點修改的代碼
因為單點修改可以通過調用區間修改函數來修改一個長度為1的區間來實現。
且純單點修改的代碼跟區間修改的幾乎相同（懶）。

主函數中的調用

int main() {int n, m, opt, l, r, k;cin>>n>>m;for(int i = 1; i <= n; i++) cin >> arr[i];build(1, n);for(int i = 1; i <= m; i++){cin>>opt>>l>>r;if(opt==1){cin>>k;change(l,r,k,1,n);}else{cout<<query(l,r,1,n);}}return 0; }

七、區間合并操作與懶標記的運用

https://www.luogu.com.cn/problem/P3372
https://www.luogu.com.cn/problem/P3373
https://www.luogu.com.cn/problem/P6242
https://www.luogu.com.cn/problem/P4198

八、權值線段樹

相信接觸過平衡樹的同學直接就看出來了：這不就是平衡樹的模板題嘛

但是在考場上寫動不動就一兩百行的平衡樹未免太折磨人了！

下面來介紹權值線段樹的寫法

在一開始的例題中，線段樹一個節點記錄的是這個節點對應的區間的數的和。在權值樹里，節點記錄的則是對應區間的數出現了幾次！
例如，對于集合 [1,3,3,5,4,8] 權值線段樹的結構為這樣：
節點記錄的是節點所代表的區間的數的出現次數，比如 [1,3,3,5,4,8] 2 中 1 出現 1次，2、6 和 7 出現 0 次，3 出現 2 次， 4 出現 1 次，5 出現 1 次，8 出現 1 次
所以葉子結點中表示的就是對應數組出現次數，其他結點代表區間內所包含數的出現次數。
那么，題目中的插入的數的值域可是有 $10^9$ 啊，怎么能開下這么多的空間?
所以，在這里不能使用堆式建樹

動態開點

從上面的圖里可以看出有一些點是不需要用到的

夸張一點：

這些黑色節點我們一開始不需要，等到需要用到的時候再開辟就可以了！

這里我先介紹競賽中比較常見的，較為容易的實現方法：
我們可以聲明一個足夠大的線段樹數組，再聲明一個變量 cnt（記錄用過的節點數）
當我們訪問到一個沒訪問過的節點時，令 cnt++，則線段樹數組中下標為 cnt 的節點即為新節點，只需要想辦法讓新節點跟以前的節點聯系上就好了

struct seg {int ls, rs, val;seg(int v=0,int l=0, int r=0):val(v),ls(l),rs(r){}; };seg t[MAX_N]; int cnt;inline void pushup(int o) {t[o].val = t[t[o].ls].val + t[t[o].rs].val; }void change(int &o, int l, int r, int k, int v) {// 將 k 的出現次數改變 v，[l, r]為當前節點代表的區間if(!o) o = ++cnt;if(l == r){t[o].val += v;return;}int mid = (l + r) / 2;if(k <= mid) change(t[o].ls, l, mid, k, v);else change(t[o].rs, mid + 1, r, k, v);pushup(o); }

這里的change 函數與前面的邏輯一致，除了這句話

if(!o) o = ++cnt;

而且這里的 o 是以引用的方式傳進來的，其實這里的o就是節點在線段樹數組中的下標
回顧代碼，在線段樹數組被聲明時，每一個節點的左右子節點都為0，那么，我們在遞歸的過程中遇到了 o 為零，就可以確定這個節點未被使用。
而以引用的方式傳入，則可確保原值被賦值，即 t[o].ls 和 t[o].rs 。
即實現了將新開辟的節點與其父節點相聯系，理解了change函數，插入與刪除操作就很簡單了
如果要插入 x ，則執行 change ( 1 , -1e9 , 1e9 , x , 1 )
如果要刪除 x，則執行 change ( 1 , -1e9 , 1e9 , x , -1 )
設區間長度為 n，則線段樹的樹高是 $l o g N$ ，在這里區間長度即是值域的大小 $2^9$ ，每次操作最多產生新節點數即是 $log(2^9)$ ，30個左右，所以空間是絕對足夠的。
如果想要追求效率的話，可以用離線算法，將所有詢問到的數記錄下來并離散化，再使用權值線段樹，感興趣的話可以自己實現一下，接下來的操作如果理解了一開始的線段樹的介紹后就是很簡單的了！

九、查找排名第k的數

訪問到一個節點時，記錄左子區間的數的次數為 num，如果 k <= num，則向左子節點遞歸；否則，將k減去num，再向右子節點遞歸。

int query_kth(int o, int l, int r, int k) {if(l == r){return l;}int mid = (l + r)/2;int num = t[t[o].ls].val;if(k <= num){return query_kth(t[o].ls, l, mid, k);}else{return query_kth(t[o].rs, mid + 1, r, k - num);} }

為什么向右子節點遞歸時k要減去 num ?
這個函數其實是求以 o 為根的樹中第 k 的數，又 num 代表的是左子區間的數的次數，那么右子區間的第 k-num 的數就是以 o 為根的子樹的第 k 的數了 .

十、查詢數 k 的排名

設當前節點代表的區間的中點為 mid ，當 k <= mid 時，向左子節點遞歸；否則，設左子區間的數的次數為num，向右子節點遞歸，再將得到的數加上 num 并返回。

int query_rk(int o, int l, int r, int k) {if(l == r){return 1;}int mid = (l + r)/2;if(k <= mid){return query_rk(t[o].ls, l, mid, k);}else{return t[t[o].ls].val + query_rk(t[o].rs, mid+1, r, k);} }

對于動態開點，vector、指針，都是可行的方法；用指針的話，可以避免類似 t[t[o].ls].val 這種寫法，但是也會帶來較大的調試難度！這里就不作更多的展開了，大家可以自己嘗試不同的寫法！

總結

以上是生活随笔為你收集整理的什么是线段树？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

线段