可持久化线段树

[Ir1d]

https://oi-wiki.org/ds/persistent-seg/

[2403772980ygy]

可持久化权值线段树严格意义上来说不是主席树, 主席树更多的是一种算法, 也就是线段树差分, 而不是一个数据结构.

gitalk好评

[thallium]

能再详细一点解释一下如何查询第k小吗，太菜了想不明白。（现在明白了）

[ouuan]

@i-Yirannn
道理我都懂，但是你花括号怎么能换行呢 ？ (

快pr一个

应该是因为大括号上一行末尾有行内注释..

[jayzhan211]

习题: CF813E

[H-J-Granger]

@accelsao
习题: CF813E

pr一个（

[YunQian-QwQ]

可持久化线段树只讲主席树有点少吧......（

[Life-Cai]

墙裂推荐此讲解视频

[myeeye]

其实可以再加上可持久化线段树实现可持久化数组吧，毕竟基于可持久化数组的可持久化并查集也是 NOI 考过的知识点。（NOI2018 归程就可以这么做。）

[aaronyen0]

想請教一下，關於可持久化DSU的部分。我先將我目前理解的部分簡單解釋一下

題目

這題應該是n個數值以及m個query，其中query分為三類

• connect(a, b)
• 返回版本k
• 確認a,b是否連通

主席樹維護DSU的部分

• build：走到葉節點，也就是區間長度只有1時，先自己指到自己
• update：先在外部決定誰是母樹，再來也是走到葉節點並將子樹接上母樹
• getRoot: 顧名思義，回傳值應為該版本該target下，DSU中應該指到的根

問題

• 令我困惑的是，非葉節點的存在意義是什麼？是否單純是為了葉節點的版本控管，因為每次merge看起來只有某個葉節點被改變？不確定是否有需要log(n)個新結點去維護一個節點的改變？
• tree[newroot].rank = std::max(tree[newroot].rank, tree[now].rank + 1);，可能是我trace code錯誤，我理解的newroot是DSU中的節點，範圍為1~n，並不是tree的idx？這樣如果退回某個版本重新做連接的話，深度是不是就開始亂掉了？
• 另外也想請教一下，有沒有那種可以 online(1)delete edge (2)connect (3)check connected 的結構？

[zero4338]

@worcdlo
想請教一下，關於可持久化DSU的部分。我先將我目前理解的部分簡單解釋一下

題目

這題應該是n個數值以及m個query，其中query分為三類

• connect(a, b)
• 返回版本k
• 確認a,b是否連通

主席樹維護DSU的部分

• build：走到葉節點，也就是區間長度只有1時，先自己指到自己
• update：先在外部決定誰是母樹，再來也是走到葉節點並將子樹接上母樹
• getRoot: 顧名思義，回傳值應為該版本該target下，DSU中應該指到的根

問題

• 令我困惑的是，非葉節點的存在意義是什麼？是否單純是為了葉節點的版本控管，因為每次merge看起來只有某個葉節點被改變？不確定是否有需要log(n)個新結點去維護一個節點的改變？
• tree[newroot].rank = std::max(tree[newroot].rank, tree[now].rank + 1);，可能是我trace code錯誤，我理解的newroot是DSU中的節點，範圍為1~n，並不是tree的idx？這樣如果退回某個版本重新做連接的話，深度是不是就開始亂掉了？
• 另外也想請教一下，有沒有那種可以 online(1)delete edge (2)connect (3)check connected 的結構？

3.https://loj.ac/p/122

[zzfhuazhui]

有大佬知道为什么，inline int getid(const int &val) { // 离散化
return lower_bound(ind + 1, ind + len + 1, val) - ind;
}中第二个参数是ind+len+1,而不是ind+n+1?当原数组中有较多的重复元素时，这样子不会漏掉一些数吗？

[STKoala]

可持久化并查集的代码在洛谷TLE。秩是不是应该为集合大小会好点，而不是最大深度。

[HeliumOI]

这份代码之所以会 TLE 是因为它把序列的下标和线段树结点的下标搞反了

[usada-pekora-286]

可持久化并查集复杂度错的。

[luowenzhangBJ]

求最大最小值没办法用前缀和啊。。。