我在空闲时间阅读了一些有趣的算法，我刚刚发现了凸包技巧算法，我们可以使用它计算给定 x 坐标上平面中几条线的最大值。我找到了这篇文章：
http://wcipeg.com/wiki/Convex_hull_trick
这里作者说，这个算法的动态版本在对数时间内运行，但没有证据。当我们插入一行时，我们测试了他的一些邻居，但是我不明白O(log N)当我们可以N通过这样的插入测试所有行时怎么会这样。是正确的还是我错过了什么？
更新：这个问题已经回答了，有趣的是下面的其余部分
先感谢您！
要回答您的第一个问题：“插入如何是 O(logn)？”，您确实可以最终检查 O(n) 个邻居，但请注意，当您发现需要执行删除操作。
关键是如果你要插入 n 行，那么你最多可以做 n 次删除操作。因此，除了每行 O(logn) 工作之外，额外工作的总量最多为 O(n)，您需要在已排序的数据结构中找到它的位置。
所以插入所有 n 行的总工作量是 O(n) + O(nlogn) = O(nlogn)，或者换句话说，每行摊销 O(logn)。
该文章声称O(log N)每次插入的摊销（不是最坏的情况）时间。摊销界限很容易证明（每行最多删除一次，每次检查要么是最后一个，要么导致删除一行）。
文章根本没有说这个数据结构支持删除。我不确定是否可以有效地处理它们。有一个障碍：时间复杂度分析是基于这样一个事实，即如果我们删除一条线，我们以后就永远不需要它了，而允许删除的情况并非如此。
插入可以比 O(log n) 更快，它可以在 O(Log h) 中实现，其中 h 是已经计算的 Hull 点的集合。可以在每个点 O(log h) 中完成批量插入或一个一个插入。你可以阅读我的文章：
关于删除：我很确定，但必须证明，它可以在每点 O(log n + log h) = O(log n) 中实现。在我的第三篇文章的末尾有一段关于它的文字。