我是FHQ单推人,但我还是得学WBLT。
引入
WBLT ( Weight Balanced Leafy Tree ) 顾名思义是 Weight Balanced Tree 和 Leafy Tree 的结合。
Weight Balanced Tree 的每个结点储存这个结点下子树的大小,并且通过保持左右子树的大小关系在一定范围来保证树高。
Leafy Tree 维护的原始信息仅存储在树的 叶子节点 上,而非叶子节点仅用于维护子节点信息和维持数据结构的形态。我们熟知的线段树就是一种 Leafy Tree。———OI-wiki
学的主要原因是FHQ的可持久化不好写好像WBLT也不好写。