# 迭代型線段樹 單點修改

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

![平常我們寫的線段樹](/files/vJfG9eaCCJqrsWM6c3Cc)

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

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

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

### 建立方式

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

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

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

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

![](/files/xOEgzdpnRJk89fMvSngx)

如上圖，我們可以發現，假設原本的陣列（假設是$$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]$$ 的答案吧

![](/files/V8VUOi7GEEIq7xinFSl1) ![](/files/AcxEuT4K8iEgqmsuek8c)

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

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

### 單點修改

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

![單點修改](/files/N8CmuuHMAQKoRKVgbmDD)

會發現當我們更改一個位置$$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$$ 的冪次啊

![](/files/6o4yKTOqOmsh6IBGkJ7v)

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

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

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

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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://wiki.sam571128.codes/data-structure/segment-tree/die-dai-xing-xian-duan-shu-dan-dian-xiu-gai.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.