社区讨论

关于二维线段树。

mmaomao
学术版参与者 3已保存回复 9

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
9 条
当前快照
1 份
快照标识符
@lobxf0ra
此快照首次捕获于
2023/10/30 04:31
2 年前
此快照最后确认于
2023/11/04 09:48
2 年前
查看原帖
四分树，线段树套线段树的两种写法究竟哪个更好？

论时间复杂度(最坏)

四分树：
O(max(n,m))\large O(max(n,m))
*最坏每次询问一个1*n或者1*m的矩形。
线段树套线段树：
O(log2n×log2m)\large O(log_2n \times log_2m)

占用空间(仅对于这题)

四分树：
O(n2)\large O(n^2)
线段树套线段树：
O(n2)\large O(n^2)
基本一样 数量级一样但是四分树常数似乎更小？
综上，
  1. 由于四分树的最坏情况无法避免，存在出题人卡的情况——如果这样的话，四分树这种写法又难写又被卡，在竞赛上岂不是没有价值
  2. 假定数据随机，那四分树的平均时间复杂度应该是多少？

回复

共 9 条回复，欢迎继续交流。

正在加载回复...