由网友(巴黎左岸╰荼靡花开つ)分享简介：我们正在寻找一个数据结构存储和分拣具有两个属性框：1.高度2.侧（方形底座）we are looking for a data structure which stores and sorts boxes which have two attributes:1. height2. side (square base)...

我们正在寻找一个数据结构存储和分拣具有两个属性框：  1.高度  2.侧（方形底座）

we are looking for a data structure which stores and sorts boxes which have two attributes: 1. height 2. side (square base)

箱子是为了具有相同属性的存储对象：  1.高度  2.侧（方形底座）

the boxes are meant to store objects which have the same attributes: 1. height 2. side (square base)

结构应能并执行以下操作：

The structure should be able to and do the following:

InsertBox（高度，侧） - 插入一个盒子从给定的属性 结构体。 RemoveBox（高度，侧） - 删除一个盒子从给定的属性 结构。 GetBox（高度，侧面） - 返回最小体积箱，其具有至少一个 最小边和高度是既定的。 复选框（高度，侧面） - 检查是否有可用于这些任何盒 属性。 InsertBox (height, side) - insert a box with the given attributes from the structure. RemoveBox (height, side) - remove a box with the given attributes from the structure. GetBox (height, side) - return the minimum volume box which has at least a minimum side and height as given. CheckBox (height, side) - checks if there's any box available for these attributes.

的数据结构应是最有效的越好。 的时间复杂度应该由参数来测量：  1.高度 - N  2.侧（方形底座） - 米

the data structure should be the most efficient as possible. the time complexity should be measured by the parameters: 1. height - n 2. side (square base) - m

我认为做到这一点的最好办法是通过RB树，以便以某种方式使用上述两种方法将在时间复杂度比（N + M），也许日志（N + M）更好。

I thought that the best way to do it is by RB Tree so in some way the methods above will be in time complexity which is better than (n+m), maybe log(n+m).

推荐答案

编辑：也许你的意思是一箱，而不是面积的三维体积。在这种情况下，简单地改变目标函数：替换的 X * Y 的用的（X ^ 2 * Y）的无处不在的答案

Perhaps you meant three-dimensional volume of a box, not area. In such case simply change goal function: replace x * y with (x^2 * y) everywhere in the answer.

考虑每个箱子侧面的 X 的和高度的是的。让我们把他们当作二维平面上，而不是用规模盒分。然后，你需要一个数据结构，可以加点，删除点，找点，并进行了特殊的 GetBox 的操作。

Consider each box with side x and height y. Let's treat them as points on 2D plane instead of boxes with sizes. Then you need a data structure that can add points, remove points, find points, and make a special GetBox operation.

在 GetBox 的操作要求找到在给定的上象限点坐标最小的产品。换句话说，你必须找到以最小的 X * Y 的为其中的 X> = A 和 Y> = B 的（一和 B 的在查询中给出）。一维的树木像RB树将不会帮助你在这里。

The GetBox operation asks to find a point in given upper quadrant with minimal product of coordinates. In other words, you have to find a point with minimal x * y for which x >= a and y >= b (a and b are given in the query). One-dimensional trees like RB tree will not help you here.

您需要使用两维树的范围查询。以下任何方式都可以使用： kd树，的四叉树， R树等，这些数据结构分为主动的积分兑换成越来越小的区域，允许修剪整个地区，在一次上查询。您的 GetBox 的是一个有效范围查询的话，这是一种天然的操作为这些树木（kd树例如）。

You need to use a two-dimensional tree with range queries. Any of the following can be used: Kd tree, quadtree, R-tree, etc. These data structures split active points into progressively smaller regions, allowing to prune whole regions at once on query. Your GetBox is efficiently a range query then, which is a natural operation for these trees (k-D tree for instance).

请注意，在 GetBox 的查询你想得一分以最小的 X * Y 的而不是简单地列举所有的人。这就是为什么你应该保持在树的每个节点，例如点的指数。换句话说，每个节点的 v 的你的树，你应该存储点内的 v 的-subtree指数以最小的产品的 X * Y 的。

Note that on GetBox query you want to get one point with minimal x * y instead of simply enumerating all of them. That's why you should maintain index of such point in each node of the tree. In other words, in each node v of your tree you should store index of the point within v-subtree with minimal product x * y.

说到复杂，kd树有最坏的情况下复杂的 O（开方（N））的范围查询，其中的 N 的是点数目前在树上。所有其他的操作都可能采取的 O（日志N）的在最坏的情况下（取决于再平衡计划，我想）。

Speaking of complexity, k-D tree has worst case complexity O(sqrt(N)) for range queries, where N is number of points currently in the tree. All the other operations are likely to take O(log N) in worst case (depends on rebalancing scheme, I suppose).