algorithm - 动态凸包技巧

Question

我在空闲时间阅读了一些有趣的算法，我刚刚发现了凸包技巧算法，用它我们可以计算给定 x 坐标上平面中几条线的最大值。我找到了这篇文章:

http://wcipeg.com/wiki/Convex_hull_trick

这里作者说，这个算法的动态版本是按对数时间运行的，但是没有证据。当我们插入一行时，我们测试了他的一些邻居，但我不明白当我们可以测试所有的 N 行时，它怎么会是 O(log N)插入。它是正确的还是我遗漏了什么？
更新:这个问题已经回答了，有趣的是下面剩下的

• 我们如何删除？
  我的意思是...如果我们删除一行，我们可能需要之前的行来重置整个船体，但该算法在插入新行时会删除所有不需要的行。
• 是否有另一种方法来解决上述问题(或类似问题，例如管理插入、删除、在 x 点或给定范围内查找最大值等查询)

提前致谢!

Answer 1

要回答您的第一个问题:“插入怎么可能是 O(logn)？”，您确实最终可以检查 O(n) 个邻居，但请注意，您只需要在发现需要时检查一个额外的邻居执行删除操作。

重点是，如果你要插入n个新行，那么你最多可以做n次删除操作。因此，除了您需要在排序的数据结构中找到其位置所需的每行 O(logn) 工作之外，额外工作的总量最多为 O(n)。

因此，插入所有 n 行的总工作量为 O(n) + O(nlogn) = O(nlogn)，换句话说，每行分摊 O(logn)。