我在空闲时间阅读有趣的算法，我发现了凸包诡计算法，我们可以在给定的X坐标上计算平面中的几条线的最大值。我发现这篇文章：
http://wcipeg.com/wiki/Convex_hull_trick
在这里，作者说，这个算法的动态版本在对数时间内运行，但没有证据。当我们插入一行时，我们测试了他的一些邻居，但我不明白当我们可以通过这样的插入测试所有的O(log N)行时，它怎么会N是对的还是我漏掉了什么？
更新：这个问题已经回答了，下面是有趣的问题
如何删除？
我是说如果我们删除一行，我们可能需要前一行来重置整个外壳，但该算法是删除所有不必要的行，当插入一个新的。
它是解决上述问题的另一种方法（或类似的方法，例如管理插入、删除、在X点或给定范围内找到最大值等查询）。
提前谢谢你！
最佳答案
回答你的第一个问题：“插入怎么可能是o（logn）？”，您确实可以最终检查o（n）个邻居，但请注意，您只需要在发现需要执行删除操作时检查一个额外的邻居。
关键是，如果要插入n行新行，那么最多可以执行n次删除操作。因此，除了要在排序数据结构中找到其位置所需的每行o（logn）工时外，额外工时的总数最多为o（n）。
因此，插入所有n行的总工作量是o（n）+o（n logn）=o（nlogn），换句话说，每行分摊o（logn）。
关于algorithm - 动态凸包技巧，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30491350/