--- tags: 109_FDCS --- # segment tree part 3 ## 什麼是持久化 持久化代表一個資料結構可以保留歷史版本 一個最簡單的方法是對於每次修改，把所有的資料都複製一次 i.e. [a475: TBD(segment)](http://203.64.191.163/ShowProblem?problemid=a475) 時間複雜度: $O(qnlgn)$ , 空間複雜度: $O(qn)$ ```cpp= int n; vector<vector<int>> ver; #define m ((l + r) >> 1) void modify(vector<int>& seg, int p, int k, int i = 1, int l = 1, int r = n) { if (p < l || r < p) return; if (l == r) {seg[i] = k; return;} modify(seg, p, k, i << 1, l, m), modify(seg, p, k, i << 1 | 1, m + 1, r); seg[i] = seg[i << 1] + seg[i << 1 | 1]; } int query(vector<int>& seg, int ql, int qr, int i = 1, int l = 1, int r = n) { if (qr < l || r < ql) return 0; if (ql <= l && r <= qr) return seg[i]; return query(seg, ql, qr, i << 1, l, m) + query(seg, ql, qr, i << 1 | 1, m + 1, r); } #undef m inline void solve() { int q, i, k, p, l, r; cin >> n >> q; ver.emplace_back(n << 2, 0); while (q--) { cin >> i >> k >> p >> l >> r; ver.emplace_back(ver.back()); // copy, O(n) modify(ver.back(), i, k); cout << query(ver.back(), l, r) - query(ver[p], l, r) << endl; // for (auto& v : ver) // debug(v); } } ``` 明顯會爆掉，可見複製不是一個好做法 --- ## 持久化線段樹 Persistent segment tree 線段樹除了用陣列實作以外也可以用指標實作 而持久化線段樹就是利用樹的性質讓修改所需的時間和記憶體都降到 $O(lgn)$ 先看個圖 ![](https://i.imgur.com/4D3aZ3p.png) 這是一個有 $n=8$ 的線段樹 當我們要對其中的第 $3$ 個元素進行修改 所經過的節點如下圖 ![](https://i.imgur.com/h18PMpN.png) 也就是說，對於一次修改，只有少數幾個節點會被更新到 講明白一點，只有最多樹高($h$)個節點會被更新到 其他節點都保持原狀 所以我們可以用動態分配記憶體的方法，對於每次修改都新開 $h$ 個點就好 再將沒有修改到的地方指回原本的節點 如下圖 ![](https://i.imgur.com/MXliF2j.png) 如果再修改第 $6$ 個點，如下圖 ![](https://i.imgur.com/B9edTc5.png) 可以看到每次都會產生新的根節點，只要保存每個根節點就可以存取所有的版本 單次修改/查詢 時間複雜度 $O(lgn)$ , 空間複雜度 $O(lgn)$ --- ## 實現 以左閉右開的持久化線段樹舉例 ### node ```cpp= struct node { int v; node *l, *r; void pull() { v = (l ? l->v : 0) + (r ? r->v : 0); } node(int x = 0): v(x), l(nullptr), r(nullptr) {} node(node* a, node* b): l(a), r(b) {pull();} }; ``` #### 成員變數 ```cpp=2 int v; node *l, *r; ``` 和一般的線段樹一樣，有問題自己去[複習](/@konchin/segment) #### pull ```cpp=4 void pull() { v = (l ? l->v : 0) + (r ? r->v : 0); } ``` 從左右節點進行更新，注意空節點的值 $= 0$ #### 建構元 node(int) ```cpp=7 node(int x = 0): v(x), l(nullptr), r(nullptr) {} ``` 用於葉節點，直接設值，左右節點為`nullptr` #### 建構元 node(node*, node*) ```cpp=8 node(node* a, node* b): l(a), r(b) {pull();} ``` 用於非葉節點，直接設左右節點，值由pull更新 ### build ```cpp= node* build(int l = 0, int r = n) { if (r - l == 1) return new node; return new node(build(l, m), build(m, r)); } ``` - 如果當前是葉節點( $r-l=1$ )，呼叫建構元node(int) - 如非則呼叫建構元node(node*, node*)，左右節點分別遞迴 ### modify ```cpp= node* modify(node* pre, int p, int k, int l = 0, int r = n) { if (p < l || r <= p) return pre; if (r - l == 1) return new node(k); return new node(modify(pre->l, p, k, l, m), modify(pre->r, p, k, m, r)); } ``` #### 引數 | pre | p | k | l | r | | ---------------- | ------------ | ------------ | ---- | ---- | | 修改前的當前節點 | 欲修改的位置 | 欲修改成的值 | 左界 | 右界 | - 當左右界不在欲修改位置時，回傳修改前的節點 - 當目前節點為欲修改節點時，呼叫建構元node(int)並回傳 - 非上述任一則表示當前節點會被更新到，但不是葉節點，所以呼叫建構元node(node*, node*)並遞迴 ### query ```cpp= int query(node* cur, int ql, int qr, int l = 0, int r = n) { if (qr <= l || r <= ql) return 0; if (ql <= l && r <= qr) return cur->v; return query(cur->l, ql, qr, l, m) + query(cur->r, ql, qr, m, r); } ``` 同一般線段樹，差別在引數要傳入欲查詢的版本的根節點 --- ## 範例 例題: [a475: TBD(segment)](http://203.64.191.163/ShowProblem?problemid=a475) ```cpp= struct node { int v; node *l, *r; node(int x = 0): v(x), l(nullptr), r(nullptr) {} void pull() {v = (l ? l->v : 0) + (r ? r->v : 0);} node(node* a, node* b): l(a), r(b) {pull();} }; constexpr int maxn = 1e5 + 5; array<node*, maxn> root; int n; #define m ((l + r) >> 1) using stree = node*; //subtree stree build(int l = 0, int r = n) { if (r - l == 1) return new node; return new node(build(l, m), build(m, r)); } stree modify(stree pre, int p, int k, int l = 0, int r = n) { if (p < l || r <= p) return pre; if (r - l == 1) return new node(k); return new node(modify(pre->l, p, k, l, m), modify(pre->r, p, k, m, r)); } int query(stree cur, int ql, int qr, int l = 0, int r = n) { if (qr <= l || r <= ql) return 0; if (ql <= l && r <= qr) return cur->v; return query(cur->l, ql, qr, l, m) + query(cur->r, ql, qr, m, r); } #undef m inline void solve() { int q, i, k, p, l, r; cin >> n >> q; root[0] = build(); for (int t = 1; t <= q; t++) { cin >> i >> k >> p >> l >> r; i--, l--; //[l, r) root[t] = modify(root[t - 1], i, k); cout << query(root[t], l, r) - query(root[p], l, r) << endl; } } ``` ## 延伸 其實不是只有線段樹可以持久化 可以觀察出來，只要是像這種用指標連結的樹 像是BST, Treap之類的都可以持久化 而一些需要用到陣列的資料結構(e.g. Disjoint set) 則可以透過實作持久化陣列來達成持久化