我正在尝试解决以下问题:
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 个索引的答案。因此，看来我必须在我的线段树中使用向量。但这会使事情过于复杂。此外，我也不确定该怎么做。
有谁能建议我更好的解决方案吗？
最佳答案
您应该使用二叉搜索树 (BST) 而不是线段树，例如 AVL、Treap、Splay 等。
首先，将所有出现的值的所有索引存储在分离的 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]对于每个查询 (x, y, k)，计算 SBT k 中落在 [x, y] 范围内的元素的数量。
对于每次更新 weight[x] = v，从 BST weight[x] 中删除 x 并将 x 添加到 BST v
时间复杂度:O(nlogn + mlogn)，其中 n 是数据的长度，m 是操作数。
空间复杂度:O(n)
关于algorithm - 查找范围内权重为 k 的项目数(包含更新和查询)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41010512/