线段树套线段树时间复杂度是单次O(log^2 n)，四分树时间复杂度是单次O(n)
by 142857cs @ 2019-12-13 07:43:29
但是有些东西线段树套线段树可能做不了，只有四分树或者kd-tree能做（四分树能做但kd-tree不行的好像也有？那太毒瘤了）
by 142857cs @ 2019-12-13 07:45:28
@[142857cs](/user/35760) 也就是说尽量写线段树套线段树呗，大佬，有没有什么二维线段树的题（模板之类的）
by Treaker @ 2019-12-13 07:46:34
@[142857cs](/user/35760) 那什么东西线段树套线段树做不了，能举个栗子吗？
by Treaker @ 2019-12-13 07:47:11
@[Binary_Search_Tree](/user/40985) 不不不，你想一想查询的时候，我如果只查询一行的话，时间复杂度瞬间就退化了。
by Treaker @ 2019-12-13 07:49:46
@[Binary_Search_Tree](/user/40985) 会退化啊
by 142857cs @ 2019-12-13 07:52:27
@[Binary_Search_Tree](/user/40985) 影响啊，那个时候，我只有查询到大小为1或者2的矩形才会返回，那不就$O(n)$甚至$O(n\log n)$了嘛
by Treaker @ 2019-12-13 07:53:22
@[Binary_Search_Tree](/user/40985) 大哥，有啥二维线段树的题嘛。
by Treaker @ 2019-12-13 07:57:47
P5620
by Binary_Search_Tree @ 2019-12-13 07:58:47
@[Binary_Search_Tree](/user/40985) 好吧。
by Treaker @ 2019-12-13 08:02:24