查找范围内权重为 k 的项目数（包含更新和查询）
Find number of items with weight k in a range (with updates and queries)
我正在尝试解决以下问题：
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：
英国夏令时 1：[0]，
BST 2: [1,3],
BST 3: [2,7],
英国夏令时 5：[4]，
英国夏令时 6：[5]，
英国夏令时 7: [6]
对于每个查询(x, y, k)，统计SBT k中落在[x, y]范围内的元素个数。
对于每次更新weight[x] = v，从BST weight[x]中移除x并将x添加到BST v
时间复杂度：O(nlogn + mlogn) 其中 n 是数据的长度，m 是操作数。
Space 复杂度：O(n)
我正在尝试解决以下问题：
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：
英国夏令时 1：[0]，
BST 2: [1,3],
BST 3: [2,7],
英国夏令时 5：[4]，
英国夏令时 6：[5]，
英国夏令时 7: [6]对于每个查询(x, y, k)，统计SBT k中落在[x, y]范围内的元素个数。
对于每次更新weight[x] = v，从BST weight[x]中移除x并将x添加到BST v
时间复杂度：O(nlogn + mlogn) 其中 n 是数据的长度，m 是操作数。
Space 复杂度：O(n)