# 線段樹 🌳✨
> 「因為我什麼都不會，我想學線段樹，所以我來寫線段樹講義！」
>
> Discord: hiya.arrrrr
> Feel free to message >_<
## 大綱
> 這裡要談的是迭代式線段樹喔～ 如果想看遞迴式的，可以去瞧瞧這篇文章！
> https://oi-wiki.org/ds/seg/
以下會分成四個小部分，先簡單介紹一下線段樹，接著是原理解說，然後是 C++ 實作程式碼，最後還有一些有趣的例題和題解，如果你趕時間的話，可以直接跳到實作部分，有加一些註釋幫助理解哦！
目前內容有單點、區間更新，懶惰標記、樹上二分等等還在準備中，之後可能還會有一些酷酷的貓樹、標記永久化之類的，敬請期待～ >_<
目錄在這邊：
[TOC]
## 簡單介紹
> 「線段樹」顧名思義，是一棵儲存線段（區間）的樹！
線段樹是一種常見的資料結構，可以讓我們快速的處理區間操作，通常會用在這種情況：
```
更新操作：給一個點或區間，將其中的值按某種方式更新。
查詢操作：給一個點或區間，查詢它的某種性質。
```
線段樹可以優化這類的操作，基本的概念是將待操作的區間切成一系列小區間，把每個區間當作一個節點，也就是說每個節點都包含了一段區間的資訊，我們在更新一個位置時就一併更新好包含它的那些節點，之後就可以透過節點的資訊來加速查詢！
線段樹有很多應用，許多看似無關的問題也可以被轉化成類似的形式。不過線段樹也有一些缺點，例如它會用到的空間比較大，而且屬性要滿足結合律才能維護。
接下來就讓我們好好探索線段樹的奧秘吧 (꒪꒳꒪)
## 原理說明
> 以下都使用左閉右開的 $[l, r)$ 來表達區間！
### 單點更新，區間查詢
讓我們從比較簡單的單點更新、區間查詢開始吧～
這裡每個節點會儲存它代表的區間的某種資訊，這種資訊要滿足如果已經有左右兩半子區間的資訊，也可以很快的合併出整個區間的資訊。例如，讓節點儲存區間的和，合併方式就是相加；讓節點儲存區間的最小值，合併方式就是取左右兩半的最小值。
不過，如果是比較困難的題目，也可能需要儲存超過一種資訊才能簡單的合併。
至於前面提到的區間切分方式，我們的做法是從編號為 $1$ 的節點代表 $[0, n)$ 開始，把每個區間一直切成兩半，分別存到編號兩倍和兩倍加一的節點，切到不能再切為止。
換句話說，如果一個區間 $[l, r)$ 的編號為 $i$，那麽它的左右兩半 $[l, \lfloor \frac {l \space + \space r} 2 \rfloor)$ 和 $[\lfloor \frac {l \space + \space r} 2 \rfloor, r)$ 的編號分別會是 $2i$ 和 $2i + 1$，而葉子節點的區間長度都是 $1$（每個葉子就是原始陣列裡的一項）。
這樣會構造出一顆二元樹，長這樣：
前面是節點的編號，後面就是它代表的區間，總共會有 $2n - 1$ 個節點。
我們把節點按照切的次數分為好多層，每段區間就是切成它下面的兩個小區間，以後更新一個位置時，就必須連帶更新垂直的一條包含它的區間，像這樣：
要更新原始陣列的 $0$ 號位置的話，塗上紅色的就是所有須要連帶更新的區間。
而計算一段區間的時候，就可以改成使用一些小區間的資訊來合併，例如下圖 $n = 8$ 的時候，要算 $[1, 6)$ 就可以用 $9, 5, 6$ 號的節點合併，算 $[3, 8)$ 就可以用 $11, 3$ 號：
這樣更新和詢問的複雜度都會正比於層數，也就是 $\mathcal{O}(\log_ 2 n)$（每層切一半嘛），更新因為就是拿垂直的一條，只會包含層數個區間，而詢問的部分會在下面詳細說明，主要是每層至多只會拿兩個區間。
這樣做會增加更新的複雜度（$\mathcal{O}(1) \Rightarrow \mathcal{O}(\log n)$），但是可以顯著降低詢問的複雜度（$\mathcal{O}(n) \Rightarrow \mathcal{O}(\log n)$），可以滿意 :D
那實際使用上，我們需要實作下面這些方法：
#### `pull`
讀入初始陣列（改變 $[n, 2n)$ 中的資訊）後建構這棵樹，也就是由葉子節點的資訊去更新其他的節點，使整棵樹中的區間資訊都是好的。
我們從編號大到小更新即可，因為子節點的編號一定比父節點來得大，這樣可以確保在更新一個節點時，用來更新的子節點的資訊已經是正確的。
#### `apply`
單點的更新，也要更新到包含該位置的區間。
我們從樹中代表修改位置的葉子節點開始，一直用 $\lfloor \frac i 2 \rfloor$ 找父節點向上改即可，因為子節點的區間一定包含在父節點之內，這樣可以確保更新到所有包含該位置的區間。
#### `query`
區間的詢問，想辦法把詢問的區間用盡量大（盡量高層）的區間去合併表示。
這裡比較複雜，為了盡量使用高層的區間，做法是：
```
不斷看剩下詢問區間的左右界處，
若其無法被父節點覆蓋則先計算並刪除，
否則直接以父節點考慮，
接下來可只考慮父節點上層的節點。
```
這樣講還是不太好懂，我們看圖解釋：
計算下面黑色區間的時候，不同顏色是每一層要加的部分，灰色部分是被更高層覆蓋的。
我們從下往上一層一層看：
```
看到最下層邊界的兩個藍色節點，
他們的的父節點代表的範圍都超出區間邊界了，
也就是無法在詢問區間中找到一個節點來覆蓋它們，
所以我們必須現在計算兩個藍色節點的值，
然後邊界就會變成第二層左邊的灰色和右邊的紅色節點，
接下來只考慮第二層以上的節點。
接著會發現左邊的灰色節點的父節點在邊界內，
所以我們可以直接用它的父節點來覆蓋它，
這層就只須要計算右邊的紅色節點，
新的邊界變成上面的兩個綠色節點，
接下來只考慮第三層以上的節點。
發現兩個綠色節點的父節點都超出邊界，
所以這層要計算兩個綠色節點的值，
然後上移後發現左右界相遇，
結束計算。
```
這樣就是計算一個區間的過程，我們可以發現按照這種模式每層最多只會存取左右界的兩個值，每加完一次都會向上跳一層，所以複雜度就會是層數 $\log n$。
不過要寫成程式碼的話，我們必須公式化地描述：
考慮詢問區間的左界 $l$，如果左界 $l$ 是右子節點（用編號的奇偶性判斷），代表 $l$ 的兄弟節點在 $l$ 左邊，也就是父節點一定會超出左界，所以要現在計算 $l$ 的值，然後新的左界就會變成 $l$ 右邊的點的父節點，也就是 $\lfloor \frac {l \space + \space 1} 2 \rfloor$。
而如果 $l$ 是左子節點，代表 $l$ 的父節點也會完整包含在範圍內，所以我們可以直接把左界變成父節點 $\lfloor \frac l 2 \rfloor$。
而右界 $r$ 的情況也類似，不過方向反過來，如果 $r$ 是偶數的話，就把它加進答案裡，然後變成 $\lfloor \frac {r \space - \space 1} 2 \rfloor$，不然是奇數的話就直接變成 $\lfloor \frac r 2 \rfloor$。
這樣這個章節就告一段落了！如果想多了解怎麼實作的話，可以先看一下程式碼部分 >_<
接著讓我們開始新一個章節吧～
### 區間更新，單點查詢
在這個章節中，我們改成處理對一段區間進行更新，而在單點進行查詢這類的問題，我們要做的其實就是交換原本 `apply` 和 `query` 中對節點的存取方式，此時每個節點儲存的值比較像是「子樹全部都有這個值」的感覺，像這樣：
如果要對黑色這段區間進行更新，按照 `query` 中的方式，塗成綠色的是我們會修改到的節點，這樣的意思是，一個節點的值就覆蓋了它下面所有的節點（紅色箭頭），也就是如果一個節點往上的任意祖先有一個值的話，代表這個節點也被更新過這個值。
所以查詢一個位置的時候，就可以像是 `apply` 一樣看垂直的一條，例如：
這是一個修改過三次（不同顏色）的例子，每一個位置往上會戳到的所有值合起來就是那個位置的值，而且因為區間的取法是一樣的，所以更新和查詢的複雜度也都是 $\log n$。
目前聽起來很完美，不過有一件很重要的事，因為我們計算答案的時候是直接按照深度順序來合併的（我們並不知道操作原始的順序），也就是說：
```
先做的操作在計算答案時不一定是先被計算的。
```
這樣就會引發一個問題，例如操作是賦值的話，一個位置的值理應要是最後一次被賦予的值，但是我們計算答案的時候無法得知哪個祖先節點中的值才是最後被更新的。所以這個做法只能處理「操作順序不影響結果」的問題，如果不滿足這件事的話，必須要改成使用下一章的懶惰標記。
另外這個做法裡葉子節點不再代表原始陣列中的值，所以如果我們某個時刻想要遍歷原始陣列的話（逐個查詢複雜度是 $\mathcal{O}(n \log n)$），我們可以實做一個 `push` 方法，由根節點開始按編號小到大把值推給所有子節點，複雜度是 $\mathcal{O}(n)$，接著就可以直接遍歷葉子節點當作原始陣列！
這樣這個章節也結束了～ 詳細使用方式也請去看看程式碼吧 >_<
### 區間更新，區間查詢（懶惰標記）
## 實作程式碼
注意下面會用到的一些位元運算：
$i \gg 1 = \lfloor \frac i 2 \rfloor$
$i \ll 1 = 2i$
$i \ll 1 \space | \space 1 = 2i + 1$
$i \space \& \space 1 = i \space \% \space 2$
主要是這樣寫~~比較帥~~常數比較小，原本不懂的話可以對照一下比較好讀～
### 單點更新，區間查詢
這裡用單點賦值，查詢區間和當作範例：
``` cpp=
struct SegmentTree {
int n;
vector<int> tree;
// 節點存在 [1, 2n)
explicit SegmentTree(int n)
: n(n), tree(2 * n) {
} // 可在此將初始陣列讀入 [n, 2n)
// 讀入初始陣列後呼叫
void pull() {
// 由大到小更新可以確保子節點的資訊是正確的
for (int i = n; --i;) // 用左右子節點相加來計算父節點的值
tree[i] = tree[i << 1] + tree[i << 1 | 1];
}
// 將陣列索引 i 賦值 val
void apply(int i, int val) {
for (tree[i += n] = val; i >>= 1;) // 編號 i + n 的葉子節點代表陣列索引 i
tree[i] = tree[i << 1] + tree[i << 1 | 1];
}
// 查詢 [l, r) 的區間和
int query(int l, int r) {
int res = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) res += tree[l++];
if (r & 1) res += tree[--r];
} // 判斷是否可被父節點覆蓋並更新邊界
return res;
}
};
```
這樣就是一棵完整的線段樹了！
並且其實只要修改一點點就可以實現不一樣的功能，例如把第 19 行改成 `for (tree[i += n] += val; ...` 就變成單點加值，或是改掉合併的方式，例如：
```cpp
...
void pull() {
for (int i = n; --i;) // 改成取左右子節點的較小值
tree[i] = min(tree[i << 1], tree[i << 1 | 1]);
}
void apply(int i, int val) {
for (tree[i += n] = val; i >>= 1;)
tree[i] = min(tree[i << 1], tree[i << 1 | 1]);
}
int query(int l, int r) {
int res = ...; // 設為一個大值
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = min(res, tree[l++]);
if (r & 1) res = min(res, tree[--r]);
} // 更新答案方式也是取較小值
return res;
}
};
```
就變成查詢區間最小值了！
不過注意如果查詢的性質不滿足交換律的話，`query` 需要修改一下：
```cpp
...
Val query(int l, int r) {
Val res_l = ..., res_r = ...; // 設為單位元素
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) res_l = combine(res_l, tree[l++]);
if (r & 1) res_r = combine(tree[--r], res_r);
}
return combine(res_l, res_r);
}
};
```
這樣可以確保合併的順序和原始陣列中的順序是一致的！
### 區間更新，單點查詢
### 區間更新，區間查詢（懶惰標記）
這邊附上作者的模板，可以自己修改 `Monoid` 實現不同的功能：
```cpp=
template<class Monoid>
struct SegmentTree {
using Val = decltype(Monoid::identity());
using Tag = decltype(Monoid::lazy_identity());
int n, h;
vector<Val> tree;
vector<Tag> lazy;
explicit SegmentTree(int n)
: n(n), h(64 - __builtin_clzll(n)),
tree(n << 1, Monoid::identity()),
lazy(n, Monoid::lazy_identity()) {
}
void _push(int i, int k) {
if (lazy[i] != Monoid::lazy_identity()) {
_apply(i << 1, lazy[i], k >> 1);
_apply(i << 1 | 1, lazy[i], k >> 1);
lazy[i] = Monoid::lazy_identity();
}
}
void _pull(int i, int k) {
tree[i] = Monoid::combine(tree[i << 1], tree[i << 1 | 1]);
if (lazy[i] != Monoid::lazy_identity())
tree[i] = Monoid::apply(tree[i], lazy[i], k);
}
void _apply(int i, const Tag &tag, int k) {
tree[i] = Monoid::apply(tree[i], tag, k);
if (i < n) lazy[i] = Monoid::lazy_combine(lazy[i], tag);
}
void push(int l, int r) {
for (int d = h - 1; d; d--)
for (int i = l + n >> d; i <= r + n - 1 >> d; i++)
_push(i, 1 << d);
}
void pull(int l, int r) {
for (int d = 1; l + n >> d >= 1; d++)
for (int i = r + n - 1 >> d; i >= l + n >> d; i--)
_pull(i, 1 << d);
}
void apply(int l, int r, const Tag &tag) {
push(l, l + 1), push(r - 1, r);
for (int x = l + n, y = r + n, k = 1; x < y; x >>= 1, y >>= 1, k <<= 1) {
if (x & 1) _apply(x++, tag, k);
if (y & 1) _apply(--y, tag, k);
}
pull(l, l + 1), pull(r - 1, r);
}
Val query(int l, int r) {
push(l, l + 1), push(r - 1, r);
Val res_l = Monoid::identity(), res_r = Monoid::identity();
for (int x = l + n, y = r + n; x < y; x >>= 1, y >>= 1) {
if (x & 1) res_l = Monoid::combine(res_l, tree[x++]);
if (y & 1) res_r = Monoid::combine(tree[--y], res_r);
}
return Monoid::combine(res_l, res_r);
}
};
struct Monoid {
static int apply(int val, int tag, int len) {
return val + tag * len;
}
static int combine(int left_val, int right_val) {
return left_val + right_val;
}
static int lazy_combine(int old_tag, int new_tag) {
return old_tag + new_tag;
}
static int identity() { return 0; }
static int lazy_identity() { return 0; }
};
```
這樣就完成了 (≧∀≦ ) ♪
Sign in with Wallet
Connect another wallet