所以，基本上，我需要一种方法来计算平面中的最大值，其中最大值的坐标严格小于一点。
一种方法是检查所有具有复杂性的点。
O(N) time, N being the number of points.
O(1) space.
另一种方法是用二进制索引树（BIT）来实现，这将带来复杂性。
O(log(max(X))*log(max(Y)) time, X being the maximum x coordinate and Y being the max y coordinate.
O(max(X)*max(Y)) space, this is the main problem, I can't afford that much space.
我想要一些具有对数复杂性和尽可能接近O（n）空间的东西。
例子：
每个点的最佳值是：
A -> 0 ( none )
B -> 2 ( A )
C -> 2 ( A )
D -> 0 ( none )
E -> 10 ( D )
最佳答案
这里有一个o（n logn）构造时间（o（n）的算法，如果您有雄心壮志并实现了一个奇特的数据结构）和空间和o（logn）时间查询。
我们的想法是用o（log n）时间插入的增量方法来解决1d问题，并使用链接的wikipedia页面上描述的标准技术来构建中心数据结构（一个平衡的二叉搜索树）。若要构建二维数据结构，请按x递增对点进行排序，然后按顺序将它们插入到1D结构中，将对1D快照的引用保存在按x排序的列表中。若要查询二维结构，请在插入point.x≥query.x的点之前对最后一个快照进行二进制搜索，然后执行1D查询。
为了解决Y轴上的1D问题，我们在平衡二叉搜索树中保持非支配点。（如果存在另一个y值较小且较大的点，则以该点为主。）若要查询，请在树中找到query.y的前身。要插入，首先查询y以确保新点不受支配。如果它是非支配的，那么插入它并在它支配之后删除点。分期插入时间为O（log N）。
关于c++ - 最大化平面中的点值，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/37764426/