学习clj的论文


重量平衡树

  • 首先是动态区间k大,普通树套树,整体二分什么的就不谈了,还可以用重量平衡树来做平衡树套线段树。
  • 然后是动态KD树,将KD树的插入删除用替罪羊思想维护就行了。
  • 然后关于持久化,替罪羊树由于是均摊复杂度,所以不能对历史版本就行可持久化的修改,随便举个例子把,如果当前这个版本的sgt是整棵树重构,然后我们一直对这个版本就行修改,那就GG了。Treap是没有问题的

后缀平衡树

后缀平衡树就相当于用平衡树来维护后缀数组。
离线算法显然是求出后缀树组,然后建。

在线算法考虑在字符串开头添加字符,即当前构造出了S的后缀平衡树,现在插入cS这个串,那么很显然和每个后缀比较第一个字符后就是比较两个已插入的串了,所以直接平衡树那样插入就行了