2080. 区间内查询数字的频率

题目：

请你设计一个数据结构，它能求出给定子数组内一个给定值的频率。

子数组中一个值的频率指的是这个子数组中这个值的出现次数。

请你实现 RangeFreqQuery 类：

RangeFreqQuery(int[] arr) 用下标从 0 开始的整数数组 arr 构造一个类的实例。
int query(int left, int right, int value) 返回子数组 arr[left…right] 中 value 的频率。
一个子数组指的是数组中一段连续的元素。arr[left…right] 指的是 nums 中包含下标 left 和 right 在内的中间一段连续元素。

示例 1：

输入：
[“RangeFreqQuery”, “query”, “query”]
[[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]]
输出：
[null, 1, 2]

解释：
RangeFreqQuery rangeFreqQuery = new RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]);
rangeFreqQuery.query(1, 2, 4); // 返回 1 。4 在子数组 [33, 4] 中出现 1 次。
rangeFreqQuery.query(0, 11, 33); // 返回 2 。33 在整个子数组中出现 2 次。

提示：

1 <= arr.length <= 105
1 <= arr[i], value <= 104
0 <= left <= right < arr.length
调用 query 不超过 105 次。

思路：

利用哈希表来储存每个值出现的下标，如下图
判断所给value是否出现在哈希表中，没有的话就返回0
找到value对应的哈希表储存的下标，然后根据二分法快用右边界-左边界就可以计算出现的频次了

语法知识：

vs.setdefault(v, [])：
这行代码直接将键 v 添加到 vs 中，并将其值设置为一个空列表，如果 v 还不存在于 vs 中。
2.for i,v in enumerate(arr):
遍历arr中的所有元素，i是下标，v是对应的值
3.bisect_right(a, right)：在列表 a 中找到 right 的插入位置，即第一个大于等于 right 的元素位置。
bisect_left(a, left)： 在列表 a 中找到 left 的插入位置，即第一个大于等于 left 的元素位置
示例：
假设：
self.ix = {1: [0, 2, 5], 2: [1, 4], 3: [3]}
value = 1
left = 1
right = 4
执行这段代码后：
value = 1 在 self.ix 中，所以 a = [0, 2, 5]。
bisect_right(a, 4) 返回 2，因为 4 应该插入2的右边，索引为2。
bisect_left(a, 1) 返回 1，因为 1 应该插入0的右边，索引为1。
2 - 1 = 1，所以返回 2，表示 value = 1 在 a 中位于 left = 1 和 right = 4 之间有 1 个元素。

代码：

class RangeFreqQuery(object):

    def __init__(self, arr):
        vs={}
        for i,v in enumerate(arr):
            vs.setdefault(v,[])//将键 v 添加到 vs 中，并将其值设置为一个空列表，如果 v 还不存在于 vs 中
            vs[v].append(i)//储存下标
        self.values=vs


    def query(self, left, right, value):
        if value not in self.values:
            return 0
        a=self.values[value]//找到对应的值的下标哈希表
        return bisect_right(a,right)-bisect_left(a,left)//二分查找计算频次