algorithm - 查找范围内权重为 k 的项目数(包含更新和查询)

Question

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

Given an array of items with integer weights (arbitrary order), we can have 2 possible operations:

Query: Output the number of items that are of weight k, in the range x to y.
Update: Change the weight of an item at a certain index to v.

例子:

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

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

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

这肯定是一个线段树问题(使用点更新)。但是，我在这里遇到了一个问题——每个段只会保存 1 个索引的答案。因此，看来我必须在我的线段树中使用向量。但这会使事情过于复杂。此外，我也不确定该怎么做。

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

Answer 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. 对于每次更新 weight[x] = v，从 BST weight[x] 中删除 x 并将 x 添加到 BST v

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

空间复杂度:O(n)