四分树，线段树套线段树的两种写法究竟哪个更好？

论时间复杂度(最坏)

四分树：

$$\large O(max(n,m))$$

*最坏每次询问一个1*n或者1*m的矩形。

线段树套线段树：

$$\large O(log_2n \times log_2m)$$

占用空间(仅对于这题)

四分树：

$$\large O(n^2)$$

线段树套线段树：

$$\large O(n^2)$$

基本一样 数量级一样但是四分树常数似乎更小？

综上，

1. 由于四分树的最坏情况无法避免，存在出题人卡的情况——如果这样的话，四分树这种写法又难写又被卡，在竞赛上岂不是没有价值
2. 假定数据随机，那四分树的平均时间复杂度应该是多少？