可持久化字典树

可持久化字典树是一种可持久化数据结构,比较懂主席树原理的应该能很快写出这种字典树,类似这种没有后效性的数据结构都是可以可持久化的。

我自己YY了一个可持久化字典树的写法,开始时将root[0] = 0, 并且nxt的空指针域用0表示(以往我的写法都是写成-1),这样设置指针域有一个好处,接下来就会明白它的妙用了。
每当插入一个字符串,我们就在原字典树上新增节点,那么就会遇到两种情况:
1. 原字典树nxt[p][c]是空指针,这种情况不能往下走,而是直接在后面新增节点
2. 原字典树nxt[p][c]不是空指针,这种情况直接往下走,并且新增节点就好了,并且将原字典树的节点复制一份给新的节点
以上两种情况如果nxt的空指针域设置值是-1时,需要特判,但是我们nxt空指针域设置的是0,这样我们只要直接执行情况2的做法即可,因为nxt[0] = 0,且num[0] = 0,0往nxt域移动仍然是0,这样直接复制一份就囊括nxt域清为空指针或者直接复制一份nxt域的作用,这里就体现了nxt指针域设置为0的好处!
同理在查找时就不用去特判一些情况,写起来就比较优美。
这里有一道题目可以练手:here  题解

 

LEAVE A COMMENT