针对做法:对于每个点开两颗线段树
个人感觉空间的分析如下:对于每个点有期望 logn\log nlogn 的不同的距离,而每个不同的距离可能会在线段树上多开 logn\log nlogn 个点,那么最后空间复杂度应该是 O(nlognlogn)O(n \log n\log n)O(nlognlogn) 的。也就是理论空间要开 172=28917^2=289172=289 倍。
但是为什么实际上需要开的空间远远小于上面分析的,还是说上面的分析并不严谨。如果是在考试中,如何分析此类问题的空间复杂度?