ningago @ 2022-07-12 18:34:56
求问一下平衡树在不考虑常数的情况下可以完全替代线段树吗（屑标题
by Usada_Pekora @ 2022-07-12 18:36:31
你说的是文艺平衡树吗？似乎可行，但是相当一部分的题目用文艺平衡树似乎不好做。
by xinggancaixukun @ 2022-07-12 18:37:01
显然不能，平衡树太难写了
by zenglu @ 2022-07-12 18:37:35
但是有些常数已经比 log 还大了
比如平衡树上二分
by Usada_Pekora @ 2022-07-12 18:37:38
线段树也是平衡树。
by 听取MLE声一片 @ 2022-07-12 18:38:39
@ningago 只听说过权值树状数组代替平衡树，没听说过平衡树代替权值树状数组
by ningago @ 2022-07-12 18:39:58
@听取MLE声一片 但支持pushup和pushdown理论上可以实现啊
by Usada_Pekora @ 2022-07-12 18:41:22
@ningago 本来线段树多维护一点信息就够难写了，你还要写文艺平衡树。
by ningago @ 2022-07-12 18:44:08
@Zyingyzzz 不难写吧（个人认为，除了push相关的都是板子
by __Seniorious__ @ 2022-07-12 18:47:30
树套树求带修区间k小时（比如P2617这题），第二维用平衡树复杂度会log^3，值域线段树只要log^2，所以大概不能吧？（逃
by ningago @ 2022-07-12 18:50:26