algorithm - 如何存储一组可变项目 `(t, p)`，以便对某些 `k` 最小化 `(n-t)*p` 的 `n` 项目进行查询是有效的？

Question

例如:给定一个包含最后更新时间 (t) 和优先级 (p) 的对象列表，当对对象进行更新时，我们希望最小化最坏的 (n - t) * p(在 n = 现在的时间)。

这不适合普通的优先级队列，因为随着 n 的增长，结果会按照从 t 升序到 p 降序的顺序变化，但是如果可以在具有数百万个不同重要性的可更新行的数据库上实现，或者在应用程序逻辑中实现完美、快速的公平排队，这样的结构可能会非常有用。

Answer 1

您可以将 Overmars--van Leeuwen 数据结构适配为动态凸包，以获得提供插入/查询/删除时间 O(log^2 n) 的数据结构。

OvL 是一个简单的想法，包含大量数据结构设计以获得它所达到的时间和空间复杂度范围。本质上，这个想法是通过非常有效的合并步骤 (O(log n)) 为上凸包问题实现分而治之的算法。当我们改变一个项目时，我们重做 O(log n) 合并步骤，总成本为 O(log^2 n)。

我没有时间打出数据结构的细节(IIRC，它们在 Overmars 合着的计算几何教科书中，虽然我没有接近我的副本)，但我会描述这之间的类比问题和计算船体。

首先考虑上层船体。假设我们有三个点 p1 = (x1, y1), p2 = (x2, y2), p3 = (x3, y3) 且 x1 < x2 < x3。如果连接 p1 和 p3 的线段在 p2“上方”，则点 p2 包含在点 p1 和 p3 的上壳中，即，

(x3 - x2) y1 + (x2 - x1) y3
--------------------------- >= y2.
         (x3 - x1)

其次，考虑由过去或现在某个时间最紧急的项目组成的紧迫性“外壳”，其中，对于项目 (t, p)，时间 n 的紧迫性是 (n - t) p，感兴趣的排序键。给定项目 i1 = (t1, p1), i2 = (t2, p2), i3 = (t3, p3) 且 p1 < p2 < p3，我们说 i2 被 i1 和 i3 包含如果，在任何时候，i1 或 i3 都比 i2 更紧急。形式上，对于所有 n，我们有 (n - t1) p1 >= (n - t2) p2 或 (n - t3) p3 >= (n - t2) p2。

包容和“高于”之间有一个类比。

在足够遥远的过去，i1 是三个项目中最紧急的。在足够遥远的 future ，i3 是最紧迫的。问题是 i2 是否曾经是最紧迫的。如果是，则存在 n 使得 (n - t2) p2 > (n - t1) p1 和 (n - t2) p2 > (n - t3) p3，并且

p3 - p2               p2 - p1
------- (n - t1) p1 + ------- (n - t3) p3 < (n - t2) p2
p3 - p1               p3 - p1

  p3 - p2         p2 - p1
- ------- t1 p1 - ------- t3 p3 < - t2 p2
  p3 - p1         p3 - p1

(p3 - p2) (-t1 p1) + (p2 - p1) (-t3 p3)
--------------------------------------- < -t2 p2,
                p3 - p1

因为第一个不等式的小数系数是非负的并且总和为 1。请注意与早期不等式的逆运算的相似之处，p 替换 x 和 -t p 替换 y。

相反，假设 i2 从来都不是最紧急的。让我们找到交叉时间 n*，其中 i1 和 i3 具有相同的紧迫性。数量n*是方程的解

(n* - t1) p1 = (n* - t3) p3

相当于

n* p3 - t3 p3 = n* p1 - t1 p1

n* (p3 - p1) = t3 p3 - t1 p1

     t3 p3 - t1 p1
n* = -------------.
        p3 - p1

在 n* 之前，i1 比 i3 更紧急(因此 i1 比 i2 更紧急)。在 n* 之后，i3 比 i1 更紧急(因此 i3 比 i2 更紧急)。在 n* 处，i1 和 i3 至少与 i2 一样紧急，因此

(n* - t1) p1 >= (n* - t2) p2
(n* - t3) p3 >= (n* - t2) p2

p3 - p2                p2 - p1
------- (n* - t1) p1 + ------- (n* - t3) p3 >= (n* - t2) p2
p3 - p1                p3 - p1

  p3 - p2         p2 - p1
- ------- t1 p1 - ------- t3 p3 >= - t2 p2
  p3 - p1         p3 - p1

(p3 - p2) (-t1 p1) + (p2 - p1) (-t3 p3)
--------------------------------------- >= -t2 p2.
                p3 - p1

提前为我忽略的所有退化案例道歉。