LeetCode 2080. 区间内查询数字的频率（哈希+二分查找）

示例 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 <= 10^5
1 <= arr[i], value <= 10^4
0 <= left <= right < arr.length
调用 query 不超过 10^5 次。

class RangeFreqQuery {
    vector<unordered_map<int,int>> presum;
public:
    RangeFreqQuery(vector<int>& arr) {
        presum.reserve(arr.size());
        presum.emplace_back(unordered_map<int,int>());
        presum[0][arr[0]] = 1;
        for(int i = 1; i < arr.size(); ++i)
        {
            presum.emplace_back(presum.back());
            if(presum[i-1].find(arr[i]) == presum[i-1].end())
                presum[i][arr[i]] = 1;
            else
                presum[i][arr[i]] = presum[i-1][arr[i]]+1;
        }
    }
    
    int query(int left, int right, int value) {
        if(presum[right].find(value) == presum[right].end())
            return 0;
        if(left == 0 || presum[left-1].find(value) == presum[left-1].end())
            return presum[right][value];
        return presum[right][value] - presum[left-1][value];
    }
};

class RangeFreqQuery {
    unordered_map<int, vector<int>> pos; // 数字出现的位置
public:
    RangeFreqQuery(vector<int>& arr) {
        for(int i = 0; i < arr.size(); ++i)
        {
            pos[arr[i]].push_back(i);
        }
    }
    
    int query(int left, int right, int value) {
        if(pos.find(value) == pos.end()) return 0;
        auto it1 = lower_bound(pos[value].begin(), pos[value].end(), left);
        auto it2 = upper_bound(pos[value].begin(), pos[value].end(), right);
        return it2-it1;
    }
};