查找范围内重量K的项目数(带有更新和查询)

Question

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

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

查询：输出重量k的项目数量，在 范围x至y。
更新：在某个地方更改项目的重量 v。

索引

示例：

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

如果我们查询重量2从索引1到3的项目数量，则答案为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. 对于每个更新权重[x] = v，从bst重量[x]中删除x，然后将x添加到bst v

时间复杂性：o（nlogn mlogn），其中n是数据的长度，m是操作数量。

空间复杂性：o（n）