線段樹

tags: Competitive Programming Note 108 師大附中校隊培訓

本文已停止更新，新版請至 WiwiHo 的競程筆記

108 師大附中校隊培訓簡報

稀疏表的缺點就是不能做修改，因為以每一個元素為起點都會有各種

$2^j$ 長的塊，造成太多塊是重疊的，因此我們希望可以不要有那麼多塊重疊，最好就是我們要可以快速知道哪些塊是疊在一起的。

用把塊分割的方式去想，整個序列列是一大塊，然後這一塊可以二等分成兩小塊（如果長度是奇數，就看你喜歡放哪一邊），每一小塊又可以再二等分，這樣一直二等分下去，到最後會分到每一塊都剩下一個元素。

這樣可以畫成一棵二元樹：根節點表示整個序列，它的左子節點表示它的左半部，右子節點表示它的右半部，然後每個節點的左子節點都表示該節點所表示範圍的左半部，右子節點表示右半部，葉節點則表示只有一個元素的區間。如此一來，每一個節點都表示一個區間，而每個節點表示的區間都完整包含了其子節點所表示的區間。

舉例來說，這是一個長度為

$9$ 的線段樹，然後奇數長的塊，我習慣在分割後把中間那個放到左邊去：

順帶一提，索引要從

$0$ 或從

$1$ 開始的實作差異不大（幾乎沒差），看習慣就好，然後區間表示也有分左閉右閉（

$[l,r]$）或左閉右開(

$[l,r)$)，實作差異也沒有很大，也是看習慣。接下來的範例都會是索引從

$0$ 開始且區間都用左閉右閉來表示。

在每一個節點上，儲存在那個區間中我們想要的答案，例如最大值、最小值、區間和……等等的，然後父節點的答案可以從兩個子節點來得到，而每個葉節點所表示的區間中都只有一個數字，所以葉節點的答案只要考慮那個數字就好。

儲存

接著來討論一下線段樹該如何儲存，二元樹有兩種存法：用指標和用陣列，除非在做動態開點，否則用陣列就可以了，會比較方便，也就是用完全二元樹（Complete Binary Tree）的存法，雖然它並不一定是完全二元樹，但線段樹的每個節點的兩子樹會是平衡的，也就是高度不差超過

$1$，因此除了它最深的那一層，其他層都會是滿的，不會造成太多空間浪費。

如果根節點的編號是

$0$，那麼節點

$i$ 的左子節點編號會是

$2i+1$，右子節點編號是

$2i+2$；如果根節點編號是

$1$，那麼節點

$i$ 的左子節點編號是

$2i$，右子節點是

$2i+1$。用哪一種就看個人習慣，接下來的範例根節點編號都是

$0$。

接著要來想一下陣列該開多大，也就是節點編號最多會用到多少。一棵有

$2^i$（

$i$ 是非負整數）個葉節點的滿二元樹，它的非葉節點會有

$2^i-1$ 個，因此它的總節點數是

$2^{i+1}-1$。線段樹的葉節點數和序列長度是一樣的，如果這個數字是

$n$，那麼葉節點會有

$n$ 個，最後一層填滿的話，應該會有

$2^{\lceil {\log }_{2}n\rceil }$ 個葉節點，因此整棵樹會有

$2^{\lceil {\log }_{2}n\rceil +1}-1$ 個節點。

如果

$n=2^i+a$，

$0<a<2^i$，那麼

$2^{\lceil {\log }_{2}n\rceil }=2^{i+1}$，

$2^{\lceil {\log }_{2}n\rceil +1}-1=2^{i+2}-1<2^{i+2}$，由此可知，

$n\times 4$ 一定會大於總節點數，因此陣列大小通常都會取

$n\times 4$。

建構

建立一棵線段樹很簡單，就一直遞迴去把區間二等分填數字就好。

為了方便理解流程，接下來都是 pseudo code。

array segment_tree; //用來存線段樹的那個陣列，用普通陣列或vector都可
array a; //序列
int n; //a的大小

//v的區間是[L,R]
void build(int L, int R, vertex v){
    if(L == R){
        segment_tree[v] = 用a[L]得出答案;
        return;
    }
    int M = (L + R) / 2;
    //把區間二等分
    build(L, M, v的左子節點);
    build(M + 1, R, v的右子節點);
}

複雜度就和節點數一樣，剛剛有算過了，是

$O(n)$。

單點修改

要做單點修改，就必須先找到表示那個點的葉節點，並且更新它和它的所有祖先。這可以用一個遞迴的方式來做：

//節點 v 的區間範圍是[L,R]，要修改的地方是pos，新值是value
void modify(type value, int pos, int L, int R, vertex v){
    if(L == R){ //找到了葉節點
        修改 v;
        return;
    }
    int M = (L + R) / 2; //[L,R]區間的中點
    //將這個區間二等分，左半的範圍是[L,R]，右半是[M+1,R]
    if(pos >= L && pos <= M) //pos在左半部
        modify(value, pos, L, M, v的左子節點);
    else //pos在右半部
        modify(value, pos, M+1, R, v的右子節點);
    根據v的左子節點和右子節點的答案更改v的答案;
}

線段樹的深度最深就是

$\lceil {\log }_{2}n\rceil$，因此遞迴次數為

$O(\log n)$，時間複雜度

$O(\log n)$。

區間查詢

如果遇到有一個節點的範圍被完整包含在查詢範圍內，就可以直接取這個節點記錄的答案，而不用往下找。這也可以用遞迴來做：

//查詢範圍是[l,r]，節點v的區間範圍是[L,R]
type query(int l, int r, int L, int R, vertex v){
    if(l == L && r == R) //[L,R]完整被查詢區間所包含
        return ans of v;
    int M = (L + R) / 2;
    if(r <= M) //如果查詢區間都在左半部，就只查左半部
        return query(l, r, L, M, v的左子節點);
    else if(l > M) //如果查詢區間都在右半部，就只查右半部
        return query(l, r, M + 1, R, v的右子節點);
    else{
        //如果查詢區間跨越兩半部，那就也把查詢區間切半
        //這樣可以確保遞迴後[l,r]一定在[L,R]之內
        return 用query(l, M, L, M, v的左子節點)
            和query(M + 1, r, M + 1, R, v的右子節點)
            得出區間[l,r]的答案;
    }
}

舉例來說，如果查詢區間是

$[2,7]$，被遞迴到的會是上圖紅色的點。如果再自己多畫幾張圖會發現，被遞迴到的點一開始會是一條線，直到表示兩個端點的葉節點的 LCA，然後開始分叉成兩條畫到兩個端點的線，還有左分叉線上的每一個節點的右子節點與右分叉線上的每一個節點的左子節點。

（示意圖）

可以發現這數量最多就差不多深度的四倍而已（如果查詢區間是整個序列），所以複雜度也是

$O(\log n)$。

懶人標記

在分塊法為了做區間修改，我們給塊打上懶人標記，線段樹也可以這麼做，概念完全一樣，只要先在節點上記錄對答案的變動，然後如果修改區間完整包含一個節點所代表的區間，那麼就可以直接用懶人標記和這個節點上記錄的答案來推算出新的答案。

要注意一點的是，如果查詢時要往下遞迴，必須要把經過節點的懶人標記往下推，這樣在查子節點的時候答案才是對的，這也沒很麻煩，就把懶人標記移到子節點上，再把父節點的答案改成用懶人標記和本來答案推出來的實際答案，然後把懶人標記拿掉就好。

至於修改的遞迴，和區間查詢大同小異：

//新值是value，修改區間是[l,r]，節點v的範圍是[L,R]
void modify(type value, int l, int r, int L, int R, vertex v){
    if(l == L && r == R){
        打懶標在v上;
        return;
    }
    int M = (L + R) / 2;
    if(r <= M) modify(value, l, r, L, M, v的左子節點);
    else if(l > M) modify(value, l, r, M + 1, R, v的右子節點);
    else{
        modify(value, l, M, L, M, v的左子節點);
        modify(value, M + 1, r, M + 1, R, v的右子節點);
    }
    用兩個子節點的答案更新v的答案;
}

含懶標的區間查詢：

//查詢範圍是[l,r]，節點v的區間範圍是[L,R]
type query(int l, int r, int L, int R, vertex v){
    if(l == L && r == R)
        return ans of v;
    把節點v的懶標下推; //<----
    int M = (L + R) / 2;
    if(r <= M)
        return query(l, r, L, M, v的左子節點);
    else if(l > M)
        return query(l, r, M + 1, R, v的右子節點);
    else{
        return 用query(l, M, L, M, v的左子節點)
            和query(M + 1, r, M + 1, R, v的右子節點)
            得出區間[l,r]的答案;
    }
}

這樣一來，區間修改的複雜度就和區間查詢一樣，是

$O(\log n)$。

動態開點

前面有提到，在動態開點的時候，會用指標來存線段樹。

當你的區間範圍非常大，像是

${10}^9$ 的時候，剛好題目讓你也很難離散化，用陣列開線段樹，記憶體一定不夠，但是你根本只會用到其中幾個節點而已，此時就可以用動態開點，只要開你需要的節點就好。

可以用一個 struct 來儲存一個節點的資料：值、懶人標記和指向兩個子節點的指標，當你遞迴到一個節點的時候才把它開出來，這樣就可以大幅省下空間。

高維線段樹

線段樹可以有很多維度，就是你在每個

$D$ 維線段樹的節點放一棵

$D-1$ 維的線段樹。

舉例來說，二維線段樹的代表

$[0,4]$ 的這個節點上有一個一維線段樹，這個一維線段樹上代表

$[2,3]$ 的這個節點，記錄的答案可以看成是二維矩陣上，左上角是

$(0,2)$，右下角是

$(4,3)$ 這個子矩陣範圍的答案。

因為在每一個節點都要往下查低一維的線段樹，所以複雜度是

$O({\log }_2^{D}n)$。

練習題

• ZeroJudge d539 - 區間詢問最大值
• ZeroJudge d799 - 區間加值、區間求和
• TIOJ 1224 - 給你一堆矩形，求這些矩形的聯集面積