0

我正在尝试解决以下问题：

给定一个具有整数权重（任意顺序）的项目数组，我们可以有 2 种可能的操作：

查询：输出权重为 k 的项目数，范围为 x 到 y。
更新：将某项索引处的权重更改为 v。

例子：

给定数组：[1,2,3,2,5,6,7,3]

如果我们从索引 1 到 3 中查询权重为 2 的项目数，那么答案将是 2。

如果我们将索引 2 处的元素修改为权重为 2，那么我们再次进行相同的查询，答案将是 3。

这当然是一个段树问题（使用点更新）。但是，我在这里遇到了一个问题——每个段只能保存 1 个索引的答案。因此，似乎我必须在我的段树中使用向量。但这会使事情变得过于复杂。此外，我也不知道该怎么做。

有人能建议我更好的解决方案吗？

4

1 回答 1

1

您应该使用二叉搜索树 (BST)，而不是分段树，例如 AVL、Treap、Splay 等。

  1. 首先，将所有出现值的所有索引存储在单独的 BST 中。在您的示例 [1,2,3,2,5,6,7,3] 中，应该有六个 BST：

    BST 1：[0]，
    BST 2：[1,3]，
    BST 3：[2,7]，
    BST 5：[4]，
    BST 6：[5]，
    BST 7：[6]

  2. 对于每个查询 (x, y, k)，计算 SBT k 中 [x, y] 范围内的元素数。

  3. 对于每个更新权重[x] = v，从 BST 权重[x] 中删除 x 并将 x 添加到 BST v

时间复杂度：O(nlogn + mlogn) 其中 n 是数据的长度，m 是操作的数量。

空间复杂度：O(n)

于 2016-12-07T07:28:53.823 回答