---
tags: PCCA
---

# Disjoint Set Union (Advanced)

## Pre-knoledge

- DSU 使用方法及實作
- 持久化線段樹 / 持久化 Treap

{%youtube 8dsEw2ndqCI%}

## 持久化 DSU

DSU 是一個相對簡單的資料結構，只需要在陣列上紀錄父節點編號和子樹大小就可以維護了。因此只要想辦法讓陣列可以持久化，就可以將 DSU 持久化。

我們可以建一顆線段樹，但是不做 pull 也不做 push，只是要利用線段樹可持久化的性質來保留歷史版本而已，將線段樹當成可持久化陣列來用。

<!--  -->

在這種情況下可以發現葉節點只需要儲存 DSU 陣列裡的內容，而非葉節點只需要儲存左右節點的指標，所以其實可以用 `union` 這種結構來進一步的壓空間，雖然大部分時間沒必要且會增加 code 的實作量。

而在實作上，因為每次修改節點都需要額外 $O(\lg N)$ 的時空，為了盡可能的減少每一個步驟改到的節點，路徑壓縮優化是沒辦法用的，所以只能透過啟發式合併來優化 DSU。

只做啟發式合併的 find/union 的時間複雜度為 $O(\lg N)$ ，而持久化線段樹每次詢問/修改的時間複雜度為 $O(\lg N)$ ，因此在持久化並查集上做一次 find/union 的時間複雜度會是 $O(\lg^2 N)$ 。

### 例題
- [ZJ b412. 【記憶中】之記憶中的并查集](https://zerojudge.tw/ShowProblem?problemid=b412) , [Pastebin 程式碼連結](https://pastebin.com/Cq6nfuYj)

---

## 可回退 DSU

一樣不進行路徑壓縮，額外儲存做過的修改讓 DSU 可以回退到修改之前的樣子。

### 時間線段樹

一種離線演算法，可以用來解決詢問與操作具有時效性的問題。
大概的思路是將線段數當成時間軸，將區間操作切成數個段落放在線段樹上，最後遍歷一次線段樹算出結果。

礙於時間關係這裡不細述，有興趣的人可以自己去搜尋看看。

#### 例題

- [CSES - Dynamic Connectivity](https://cses.fi/problemset/task/2133/)
- [CF - EduR 22 F. Bipartite Checking](https://codeforces.com/contest/813/problem/F)
- [TIOJ - 1903 . 【Gate】這個笑容由我來守護 - EXTREME](https://tioj.ck.tp.edu.tw/problems/1903)