关于此题复杂度的一点疑惑
查看原帖
关于此题复杂度的一点疑惑
128606
2018ljw一般路过HL人楼主2024/7/17 12:18

众所周知,这类题目修改会暴力下放到叶子底部。对于叶子的修改复杂度是 O(nlog⁡nlog⁡V)O(n\log n\log V)。

但线段树做修改操作时,还会存在一些被直接 return 掉的区间。

目前个人理解是,每个下放到叶子节点的修改,在每层至多产生一个 return 掉的区间。因此这些区间个数是三个 log 的。

想问问有没有什么问题/哪里有问题。

如果是 2 个 log 或更少的话如何证明/kel

2024/7/17 12:18
加载中...