- 李超线段树的时间复杂度和空间复杂度分别是多少?
我自己分析了一下,感觉时间是 O(nlogn) 的,空间是 O(n) 的,但是之前听有人说时间是 O(nlog2n) 的?
空间复杂度我自己分析出来感觉也有点怪怪的,如果按照这样分析,标记永久化的动态开点线段树空间复杂度应该也是 O(n) 的?
网上大部分李超线段树的教程好像都没有提及它的时空复杂度。
- 有没有李超线段树不能解决的动态凸壳问题?
目前我见到的维护动态凸壳的题目好像基本上化一下式子都可以变成李超线段树可以使用的形式(相当于是原来的 (a,b) 变成了 y=ax+b ),我想问一下有没有不能转化成李超线段树的动态凸壳问题?如果没有,那平衡树维护动态凸壳的算法现在是不是没有太大的意义(李超线段树相当于是在线算法,时空复杂度两者一样(如果上面的分析没有问题的话),李超线段树常数还小)?
注:查询斜率和插入点横坐标都单调的那一种不在考虑范围内,那一种可以直接单调队列维护。