# 迭代DFS迭代式線段樹（時間線段樹）
## 前言
**第一次寫這種文章，如果寫得不清楚還請見諒**
如果還不知道什麼是線段樹（遞迴版和迭代版）建議先去看過遞迴版的再來。至於迭代版可以參考這兩篇，我用的迭代式線段樹結構和他們比較類似，和原版的zkw有點差距：
https://omeletwithoutegg.github.io/2019/12/07/Iterative-SegmentTree/
https://codeforces.com/blog/entry/18051
另外最好也要熟悉位元運算，不過既然都會用迭代式線段樹應該就不會對位元運算有問題了(?
## 時間線段樹
對於可以退回上一步操作 (undo) 的資料結構，可以使用將操作依照時間線段拆成好幾個節點，以 [TIOJ1903](https://tioj.ck.tp.edu.tw/problems/1903) 為例：
> 給定一張 $N$ 個點 $M$ 條邊的圖（可能有重邊），有$Q$筆操作，每筆操作符合下列一種情形：
>
> - 加入一條邊
> - 刪除一條邊
>
> 對於每筆操作，輸出這張圖的連通塊數量 ($N,\ M+Q \leq 5 \times 10^5$)
很顯然，輸出連通塊數量會用到併查集，問題是如何用併查集維護針對時間改變的操作。簡化問題為：
> 給定一張 $N$ 個點 $M$ 條邊的圖（可能有重邊），有 $Q$ 筆操作，每筆操作符合下列一種情形：
>
> - 加入一條邊
> - 移除上一條被加入的邊 (undo)
>
> 對於每筆操作，輸出這張圖的連通塊數量
如果併查集只使用啟發式合併，那每次操作最多只會改到：
- 其中一點指向的連通分量
- 其中一點的深度
那麼，針對這些改動的部分，可以用一個 stack 維護，就可以執行 undo 操作了。
回到原本的問題，如何將每次操作都轉變成可以用 undo 維護的形式呢？注意到每條邊都有一段存在的時間，可以利用線段樹的區間修改將這個時間區間拆成好幾個小區間，存在節點裡；換句話說，就是對時間軸開線段樹。
上圖就是將 \[2, 7\] 這段區間拆成線段樹的節點(黃色)儲存於線段樹中。最後，對整棵線段樹DFS一次，到達葉節點時就是該時間的情形。
大致上寫成偽代碼：
```cpp=
struct SegmentTree {
struct DisjointSet { // 併查集
vector<int> master, depth;
stack<pair<pair<int, int>, bool>> operations;
int count; // 連通塊數量
void init(int n);
int find(int n); // 不能路徑壓縮
void combine(pair<int, int> edge);
void undo();
};
DisjointSet graph;
vector<vector<pair<int, int>>> tree;
void build(int n) {
tree.resize(n << 2);
return;
}
void add_edge(int l, int r, int v, int tl, int tr, pair<int, int> edge) {
int m = l + r + 1 >> 1;
if (l == tl && r == tr) tree[v].push_back(edge);
else if (tr <= m) add_edge(l, m, v << 1, tl, tr, edge);
else if (tl >= m) add_edge(m, r, v << 1 | 1, tl, tr, edge);
else add_edge(l, m, v << 1, tl, m, edge), add_edge(m, r, v << 1 | 1, m, tr, edge);
return;
}
void dfs(int l, int r, int v) {
int m = l + r + 1 >> 1;
for (const auto& edge : tree[v]) graph.combine(edge);
if (l + 1 == r) printf("%d\n", graph.count);
else dfs(l, m, v << 1), dfs(m, r, v << 1 | 1);
for (int i = 0; i < tree[v].size()) graph.undo();
return;
}
};
```
對於各種支援 undo 操作的資料結構都能套用這個技巧。
## 迭代式線段樹Ver.
當然，不只遞迴式的線段樹可以這麼做，迭代式的應該也能這麼做。然而，迭代式的在 DFS 時有一些限制，如果是用上面連結的迭代式線段樹，如果大小不是 2 的冪次，它會有這種詭異的情況：
這是大小為 7 的情況，被拆成大小為 4, 2, 1 的完美二元樹了，如果覺得這很漂亮，可以參考一下大小為 13 的情況（圖源是上面的連結）：
嗯，被拆成以 2 為根大小為 8 、以 7 為根大小為 2 、以 12 為根大小為 2 、以 13 為根大小為 1 的完美二元樹了。它可能包含某些規律，但真的有必要找到嗎？
### 限制
一般來說，迭代式線段樹的操作是由下向上的，以區間查詢舉例：
```cpp=
int query(int l, int r, int t) {
int ans = 0;
for (l += size, r += size; l < r; l >>= 1, r >>= 1) {
if (l & 1) ans += tree[l++];
if (r & 1) ans += tree[--r];
}
return ans;
}
```
顯然是由下而上的。
然而，時間線段樹有一個自然的限制：必須按照「由上向下」的順序遍歷。因為資料結構一次只退一步的關係，不可能單純地由下向上。換句話說，遍歷的順序被限制了。所以說，上面的方法被限制了（因為結構不連續），除非有人能想到方法適應這個奇怪的結構。
### 解決方案
既然不能使用那種奇怪的結構，那當然還是開滿完美二元樹。
現在線段樹的 struct 裡面儲存兩個值：`size` 和 `_size` ，分別表示原始的資料量和大於等於這個數，最小的 2 的冪次。簡單寫成程式碼：
```cpp=
int _size = 1;
while (_size < size) _size <<= 1;
```
現在可以使用普通遞迴的 dfs 遍歷這棵樹了。以後開樹時大小改用 `size + _size` 或者 `_size << 1`，其他操作基本上不變（區間修改相關的也要改成 `_size`）。
## 迭代 Ver.
然而，寫迭代式線段樹的幾個理由，其中一個就是避免遞迴，壓低常數。結構都開成完美二元樹了，一定有什麼漂亮的迭代方式 DFS 整棵樹吧。
DFS 時有四個階段要考慮：
1. 向下到達葉節點
2. 執行在葉節點的操作
3. 退回到某節點
4. 如果原本在左節點，則換到右節點，執行 1. 2.
第一步是向下到達葉節點，向下的過程好辦。令當前節點為 `node` ，只需要在迴圈裡一直 `node <<= 1` 就行。停止的條件和遞迴不同，遞迴時有左右界可用，因此可以有`l == r + 1`跳出的條件，如果在迭代時不紀錄樹高或左右界等等的資訊就沒有這項條件可用。然而，有個更簡單的判斷方式：
觀察整棵樹的結構（數對是入點及出點時間戳）
資料只會記錄到 size + \_size - 1 ，這是迭代式線段樹特有的，如果觀察遞迴的線段樹，它會有一些空隙。
\
因此：
```cpp=
for (; node < _size + size; node <<= 1) {
/*
for(auto &operation: tree[node]){
執行單次操作
}
*/
}
```
這就是向下到葉節點的過程。第二個步驟滿顯然的，只是如果有必要使用節點編號必須使用 `node >> 1` ，因為跳出前會多執行一次 `node <<= 1` 。並且要注意仍然有可能跳到非葉節點的部分 (\_size<= node < \_size + size)
\
第三步比較難想，給一張圖可能比較好懂：
黃線從左邊一路看到右邊，鉛直的部分就是要後退的時候。如果將下面的節點編號都減去 `_size` 再 +1 答案會非常顯然（代表它在下排的第幾個）：每當到達 `node` 時，必須後退 `log2(node-_size+1 的因數中最大的 2 的冪次)+1`。
如果對 BIT 夠熟應該可以知道中間 2 的冪次可以用 lowbit 求。但那不是重點，因為如果再稍微推理一下，應該可以發現除了最後一次退回，退回次數都符合「二進位下， `node` 尾端的 1 的數量 +1」。
:::info
### 說明
對於原先的數 `node - _size + 1` ， `node - 1` 相當於 `(node - _size + 1) + (_size - 1)`，因此`node - _size + 1`後面都是 0 的部分都會變成 1 ，當遇到 `node - _size + 1` 的第一個 1 時會變成 0 。
以 `node = 5, _size = 4` 為例， `node - _size + 1 = 2 = 010 (2)`，`_size - 1 = 3 = 011 (2)`，所以相加之後原本 `node - _size + 1` 後面是 0 的部分都變成 1 ，所以最後一位是 1 。而遇到倒數第二位時則因為進位，該位變成 0 。
```
010
+ 011
_____
101
```
但是最後一個數沒有這個性質可以用：最後一個數會是 `100000...` 因此加上 `_size - 1` 時，第一個 1 吃不到 `_size - 1` 的那些 1 。以 `node = 7, _size = 4` 舉例， `node - size + 1 = 4 = 100 (2)`, `_size - 1 = 3 = 011 (2)`
```
100
+ 011
_____
111
```
雖然後面兩位都確實因為 `011` 變成 1 了，但是第一位吃不到 1 所以還是還是維持 1 。
:::
至於「多一次」的實現方式，我偏好用 `do-while` 迴圈，只要能實現相同效果的方式都可以。
```cpp=
do {
node >>= 1;
/*
for(int i = 0; i < operations.size(); i++){
undo();
}
*/
} while (node & 1)
```
\
第四步在原先的迭代式線段樹裡可以用`node ^= 1`，但因為必定是從左子節點到右子節點所以可以用 `node |= 1` ，我覺得比較好按.jpg
\
最後，要判斷的是何時結束遍歷，否則當 `node` 回到 1 時，會再遍歷一次。因此，再使用一次 `do-while` 迴圈，判斷第二次 `node == 1` 時就跳出。寫成模板：
```cpp=
int node = 1;
do {
for (; node < size + _size; node <<= 1) {
// do
}
if ((node >> 1) >= _size) // leaf: node >> 1
do {
node >>= 1;
// undo
} while (node & 1);
node |= 1;
} while (node > 1);
```
使用這個模板要特別注意的是，因為最後會多退回一次（根據第三步的說明）如果在 0 這個節點會有特別影響的，可以提前跳出迴圈。
Sign in with Wallet
Connect another wallet