用线段树直接维护二维区间加的时间复杂度怎么算？

P3397 地毯

我是人999 @ 2022-07-12 16:41:02

如题，在这篇讨论中有大佬指出“四分树”可以被卡成 O(n)，但是我 bdfs 关键词四叉树 时间复杂度只找到说单次操作 O(\log n) 的博客。问题如下：

  1. 四叉树单次操作的时间复杂度到底是多少？

  2. 然后假设 n = m，用树状数组套线段树做这题的时间复杂度是不是 O(n^2\log^2n)？（抱歉不会严谨问法）

by Yahbim @ 2022-07-12 16:49:35

@我是人999 树套树是 O(n\log^2 n) 的，四叉树不知道，好像就是 2D-tree，那么好像是根号的？

by 我是人999 @ 2022-07-12 16:52:56

@Yahbim 感谢您的回答

by unsigned_short_int @ 2022-07-13 12:51:12

不太明白为什么四叉树带根号而不是 \mathrm{log_4} 之类的

by unsigned_short_int @ 2022-07-13 21:49:38

@我是人999

|