针对这道题的算法题解区的大佬们已经写的很详细了。
我想补充一点关于可持续化trie树的一些基本逻辑
关于“分裂”的理解，我和答主有不同观点。“分裂”在这里也可以理解为“开辟”一个新的节点，所有不管什么情况都要开辟一个新的节点来保存前缀和a[i]第k位v的值，所以不存在需要分情况讨论是否分裂的问题。需要分两种情况讨论的是：第1种情况，如果在当前k位存在上一个节点（即p非零值），那么就需要把p的信息（新节点没有的信息）复制给新节点；第二种情况，如果当前k位不存在上一个节点（即p为零），则不需要把p的信息复制给新节点。 if(p) tr[q][~v] = tr[p][~v]; tr[q][v] = ++ idx; Y总的这两句代码，就维护了以上两种情况。
我同意你的看法
对于一个结点，看它对应的边有无结点来表示有没有这条边直接就精髓了属于是
牛逼
补拙
关于“分裂”的理解，我和答主有不同观点。“分裂”在这里也可以理解为“开辟”一个新的节点，所有不管什么情况都要开辟一个新的节点来保存前缀和a[i]第k位v的值，所以不存在需要分情况讨论是否分裂的问题。需要分两种情况讨论的是：第1种情况，如果在当前k位存在上一个节点（即p非零值），那么就需要把p的信息（新节点没有的信息）复制给新节点；第二种情况，如果当前k位不存在上一个节点（即p为零），则不需要把p的信息复制给新节点。
if(p) tr[q][~v] = tr[p][~v]; tr[q][v] = ++ idx;
Y总的这两句代码，就维护了以上两种情况。
我同意你的看法
对于一个结点，看它对应的边有无结点来表示有没有这条边直接就精髓了属于是
牛逼