> For the complete documentation index, see [llms.txt](https://wiki.sam571128.codes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://wiki.sam571128.codes/data-structure/segment-tree/die-dai-xing-xian-duan-shu-dan-dian-xiu-gai.md).

# 迭代型線段樹 單點修改

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

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

![平常我們寫的線段樹](https://2150585595-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MWtKTigydtaqFwIlq7l%2Fuploads%2FQGGvO4h6twTpw6DBjaIC%2Fzkw_segment_tree.png?alt=media\&token=3a1c58ef-46b4-4158-b2ad-317684233e7e)

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

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

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

### 建立方式

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

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

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

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

![](https://2150585595-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MWtKTigydtaqFwIlq7l%2Fuploads%2F2vh2aCbUzGTryj2h7CoT%2Fzkw_array.png?alt=media\&token=c4b25df4-1312-43c3-b3b4-e269c6467b27)

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

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

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

{% code lineNumbers="true" %}

```cpp
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]);
    }
}
```

{% endcode %}

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

### 區間詢問

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

![](https://2150585595-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MWtKTigydtaqFwIlq7l%2Fuploads%2FfUF2OWBYjz7cyPwt6onK%2Fzkw_query.png?alt=media\&token=ef875d7b-0547-45ec-a5e0-c957686b2b56) ![](https://2150585595-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MWtKTigydtaqFwIlq7l%2Fuploads%2FhXodXa15D1rtDcrPJQKG%2Fzkw_query_2.png?alt=media\&token=b1386455-2f52-4fd7-99c0-a5e50f32382c)

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

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

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

```cpp
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)$$ 的寫法

```cpp
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;
}
```

### 單點修改

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

![單點修改](https://2150585595-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MWtKTigydtaqFwIlq7l%2Fuploads%2Foc8cDeqeA2lmdJU6JBrZ%2Fzkw_update.png?alt=media\&token=e2d19534-9f90-4bdf-b9b6-dd68570ba3da)

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

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

```cpp
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)$$

### 沒有交換律的合併函數？

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

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

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

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

```cpp
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$$ 的冪次啊

![](https://2150585595-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MWtKTigydtaqFwIlq7l%2Fuploads%2F7KkzzSgpJ0qN3lRgZGJg%2Fzkw_not_2n.png?alt=media\&token=4bba1d1b-a7f2-4063-b51c-fbb6255d0bc9)

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

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

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

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