迭代型線段樹單點修改

覺得遞迴很麻煩嗎? 想要用很短的 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]$ 的答案吧

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

對於一個區間 $[l,r]$ ，我們會將其拆成一些樹上節點，使得這些節點包含所有 $[l,r]$ 內的元素
當 $l$ 是左孩子時，他或者他的祖先會被詢問到。反之，他的祖先不會被詢問到
當 $r$ 是右孩子時，他或者他的祖先會被詢問到。反之，他的祖先不會被詢問到
當 $l$ 是左孩子時，可以直接往上找答案。反之，我們要將 $l$ 的答案獨自計算，並將 $l := l+1$
當 $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);
}