关于01trie和权值线段树的相似性
  • 板块学术版
  • 楼主金珂拉
  • 当前回复6
  • 已保存回复6
  • 发布时间2021/6/6 16:36
  • 上次更新2023/11/4 22:14:19
查看原帖
关于01trie和权值线段树的相似性
147670
金珂拉楼主2021/6/6 16:36

在01trie上维护一些信息是不是就相当于一颗动态开点权值线段树?

像是主席树可以用可持久化01trie做,线段树套平衡树可以用01trie套01trie做,树状数组套主席树也可以替换成01trie。

而且把0到N-1的节点都插入树后,Trie几乎和一个1-N的线段树同构

所以这两种数据结构本质上是不是一样的?(如果不考虑01trie的位运算能力)

2021/6/6 16:36
加载中...