迭代型線段樹 單點修改

覺得遞迴很麻煩嗎? 想要用很短的 code 寫出線段樹嗎? 那就來試試看迭代型線段樹吧!

在閱讀這篇文章前，建議先去學習遞迴型的線段樹。本節內容可能會預設讀者已經會遞迴版本的線段樹。

平常我們寫的線段樹

為什麼要用迭代型的線段樹？

迭代型線段樹（又名 zkw 線段樹），事實上就是把我們平常寫的遞迴型線段樹，用迴圈的方式實作。而這樣子的線段樹，雖然比起遞迴型，可能並沒有那麼直覺。不過實際了解過後，會發現程式碼寫起來十分短，甚至在遞迴型的線段樹得到 TLE 時，可以做為其中一種壓常的方法。

而所需的空間也只要$2n$，比起遞迴型一般開到$4n$還要節省空間（雖然遞迴型也有 $2n$寫法）

建立方式

首先，我們先從最簡單的操作開始說起吧。與遞迴版本的線段樹十分相似，我們先假設現在陣列的數字數量是 $2^k$。那麼，我們就會建立出一棵完美二元樹。

由於我們的結構是一棵完美二元樹，這種二元樹的特點是，當我們放到陣列上時。編號方式十分簡單。假設目前節點的編號為 $i$，則左孩子的編號為 $2i$，右孩子的編號為 $2i+1$。

而這棵樹的大小為 $2^{k+1}-1$，也就是$2n-1$

到目前為止的部分大致上都與遞迴版本相同。不過，讓我們觀察一下這棵樹

如上圖，我們可以發現，假設原本的陣列（假設是$a$）長度為 $n$，則$a[i]$的值，會被存在線段樹上，編號為 $i+n-1$ 的位置上。

而剩下的節點，其實我們只要從下往上，從左右孩子合併資料即可

因此，我們得到了這棵線段樹的建立方式，十分簡單

const int N = 1e5+5;
int tr[N*2], arr[N];

void init(int n){
    for(int i = 1;i <= n;i++){
        tr[i+n-1] = arr[i];
    }
    for(int i = n-1;i >= 1;i--){
        tr[i] = combine(tr[i<<1], tr[i<<1|1]);
    }
}

時間複雜度：$O(n)$​

區間詢問

接著，我們先來談談，如何尋找區間 $[l,r]$ 的答案吧

觀察一下上面這兩張圖，我們會發現幾件事情

1. 對於一個區間 $[l,r]$，我們會將其拆成一些樹上節點，使得這些節點包含所有$[l,r]$ 內的元素

2. 當 $l$ 是左孩子時，他或者他的祖先會被詢問到。反之，他的祖先不會被詢問到

3. 當 $r$ 是右孩子時，他或者他的祖先會被詢問到。反之，他的祖先不會被詢問到

4. 當 $l$ 是左孩子時，可以直接往上找答案。反之，我們要將 $l$ 的答案獨自計算，並將 $l := l+1$

5. 當 $r$ 是右孩子時，可以直接往上找答案。反之，我們要將 $r$ 的答案獨自計算，並將$r := r-1$

據上面幾點觀察，我們可以寫出一個很神奇的區間查詢的程式碼

int query(int l, int r){
    int res = 0;
    for(l+=n-1, r+=n-1;l <= r;l>>=1,r>>=1){
        if(l&1) res = combine(res, tr[l++]);
        if(r&1^1) res = combine(res, tr[r--]);
    }
    return res;
}

上面的這段程式碼，就是這種線段樹的區間詢問了，根據我們剛剛的幾點觀察所得到的

這樣子的時間複雜度可以很輕易地發現會是$O(\log n)$​

而上面這個寫法是對於閉區間的$[l,r]$ 寫法，會發現我們對 $l$ 和 $r$ 所在的節點有不同的操作。

為了方便以及美觀，更常見的寫法如下，而這個寫法是開區間 $[l,r)$ 的寫法

int query(int l, int r){
    int res = 0;
    for(l+=n-1, r+=n-1;l < r;l>>=1,r>>=1){
        if(l&1) res = combine(res, tr[l++]);
        if(r&1) res = combine(res, tr[--r]);
    }
    return res;
}

單點修改

比起區間詢問，單點修改就簡單許多了。

單點修改

會發現當我們更改一個位置$x$ 時。實際會被更改到的位置其實是他的所有祖先，因此，直接修改 $x$

接著直接去修改所有祖先即可

void update(int pos, int val){
    pos += n-1;
    tr[pos] = val;
    for(int i = pos>>1;i >= 1;i >>= 1){
        tr[i] = combine(tr[i<<1], tr[i<<1|1]);
    }
}

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

沒有交換律的合併函數？

在使用線段樹時，如最大連續和等應用。

我們時常會遇到不存在交換律的合併函數。

此時，如果直接使用上面這種寫法，會導致計算錯誤。

有個方法可以處理這件事情，也就是分開處理左界經過的節點和右界經過的節點

int query(int l, int r){
    int resl = 0, resr = 0;
    for(l+=n-1, r+=n-1;l < r;l>>=1,r>>=1){
        if(l&1) resl = combine(resl, tr[l++]);
        if(r&1) resr = combine(tr[--r], resr);
    }
    return combine(resl, resr);
}

如果 $n$ 不是 $2$ 的冪次怎麼辦？

有仔細想過上面這個做法的人，應該會很好奇一件事情。

這棵線段樹可以直接用這樣子的方式去寫，應該是因為建出來的樹剛好是完美二元樹吧

不可能每個題目都那麼剛好的給你 $n$ 都是 $2$ 的冪次啊

上圖為一個$n=5$的情況時的範例。圖中，我們一樣照著完美二元樹的方式建這棵樹。

會發現到一件很神奇的事情，有兩個節點實際上是空節點！

如果實際去考慮區間詢問的過程，就會發現我們實際上根本不會使用到那兩個空節點

而不論 $n$ 的大小為何，這些操作都依然滿足，因此我們可以直接依照完美二元樹的方式去寫！