algorithm - 在每次插入后从最后 K 个元素中找到最小值，其中 K 在小于 O(n) 的时间内不固定

Question

在每次插入后，从最后 K 个元素中找到最小值，其中 K 不固定:

例如给定数组10 2 4 1 3

Query K = 3
ans : 1 (minimum of 4 1 3)

Insertion : 5
10 2 4 1 3 5
Query K =2
ans = 3

Insertion 2
10 2 4 1 3 5 2
Query K =4
ans 1

是否有一种有效的方法可以在每个查询的 O(n) 时间内处理此类查询？

Answer 1

我假设您一开始就知道应插入的元素的最大数量，以便您可以相应地为它们分配空间。

那么最小线段树就可以工作了。最初线段树中的所有元素都包含“INT_MAX”值。

随着新元素的到来，相应的叶子(及其祖先)得到更新。选择用于更新的叶子是根据流中元素的位置。

然后可以轻松执行区间查询。

插入和查询操作都需要 O(log n) 时间。