最近在做线段树的题,对动态开点的时空复杂度有些疑惑。
我以前以为,假设操作总数为 nnn ,定义域大小为 kkk ,那么总复杂度就是 O(nlog(k))O(nlog(k))O(nlog(k)) 。但是不久前我动态开点跑不过一道 n=1e5n=1e5n=1e5 , k=1e18k=1e18k=1e18 的题……题解里也没有动态开点的。
就很疑惑,上面这个复杂度真的是对的么??