众所周知,这类题目修改会暴力下放到叶子底部。对于叶子的修改复杂度是 O(nlognlogV)O(n\log n\log V)O(nlognlogV)。
但线段树做修改操作时,还会存在一些被直接 return 掉的区间。
目前个人理解是,每个下放到叶子节点的修改,在每层至多产生一个 return 掉的区间。因此这些区间个数是三个 log 的。
想问问有没有什么问题/哪里有问题。
如果是 2 个 log 或更少的话如何证明/kel