有什么方法可以使用线段树找到给定范围内数字的频率吗？
Is there any way to find frequency of a number in a given range using segment tree?
假设，我有一个数组 [1, 2, 3, 5, 5, 6, 5, 5]
现在，可以有两种操作。其中之一是 "update" 操作，即将索引 4[1 based indexing] 中的值增加 X。另一个操作是 "query" 操作，给定一个范围，假设 [4, 8](both包含）和一个值假设为 5。现在找到值 5 在给定范围 [4, 8] 中的频率。在这种情况下，答案应该是 4.
如何使用线段树执行此 "query" 步骤？
提前致谢。
我有两个解决方案，但没有使用线段树
第一个解决方案：
将每个查询拆分为 freq(r,x)-freq(l-1,x)
迭代输入并将计数存储在数组中（或映射 if
范围很大)
如果有人查询您的职位，add/subtract
array 如果元素足够小，这应该在 O(n + q) 中工作
对于数组或 O(n + q log n) 如果你需要使用 map.
第二种解决方案：
使用 Mo's Algorithm 来解决时间复杂度为 O((N + Q) * sqrt(N) * F).
的问题
假设，我有一个数组 [1, 2, 3, 5, 5, 6, 5, 5]
现在，可以有两种操作。其中之一是 "update" 操作，即将索引 4[1 based indexing] 中的值增加 X。另一个操作是 "query" 操作，给定一个范围，假设 [4, 8](both包含）和一个值假设为 5。现在找到值 5 在给定范围 [4, 8] 中的频率。在这种情况下，答案应该是 4.
如何使用线段树执行此 "query" 步骤？
提前致谢。
我有两个解决方案，但没有使用线段树
第一个解决方案：
将每个查询拆分为
freq(r,x)-freq(l-1,x)迭代输入并将计数存储在数组中（或映射 if
范围很大)如果有人查询您的职位，add/subtract array 如果元素足够小，这应该在 O(n + q) 中工作
对于数组或 O(n + q log n) 如果你需要使用 map.
第二种解决方案：
使用 Mo's Algorithm 来解决时间复杂度为 O((N + Q) * sqrt(N) * F).