关于01Trie树整体加操作的疑问
  • 板块学术版
  • 楼主THUD
  • 当前回复7
  • 已保存回复12
  • 发布时间2024/6/26 13:41
  • 上次更新2024/6/26 18:03:09
查看原帖
关于01Trie树整体加操作的疑问
319995
THUD楼主2024/6/26 13:41

在用01Trie切了平衡树的题后感觉信心满满决定研究一下01Trie的其他用法
链接 在OIWIKI中提到01Trie树是支持整体加1操作的,但是蒟蒻反复通读几遍后还是没理解,直接把WIKI上给出的代码CV到本地也没跑出正确结果,求各位大佬解释一下
另外把这个问题丢给AI后AI给出了一种懒标记的做法,本人还没测试过不知正确性如何,不过感觉没什么意义,加了懒标记之后还不如用线段树,或者可以把01Trie树理解成一种特殊的动态开点线段树?但是用类似后缀树的方式的01Trie可以把空间压到 O(n)O(n),能比线段树省一点,具体参考P6136的第一篇题解
动态开点线段树甚至主席树可能也可以这么干

2024/6/26 13:41
加载中...