Design a data structure to find the frequency of a given value in a given subarray.

The frequency of a value in a subarray is the number of occurrences of that value in the subarray.

Implement the RangeFreqQuery class:


	RangeFreqQuery(int[] arr) Constructs an instance of the class with the given 0-indexed integer array arr.
	int query(int left, int right, int value) Returns the frequency of value in the subarray arr[left...right].


A subarray is a contiguous sequence of elements within an array. arr[left...right] denotes the subarray that contains the elements of nums between indices left and right (inclusive).

&nbsp;
Example 1:

Input
["RangeFreqQuery", "query", "query"]
[[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]]
Output
[null, 1, 2]

Explanation
RangeFreqQuery rangeFreqQuery = new RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]);
rangeFreqQuery.query(1, 2, 4); // return 1. The value 4 occurs 1 time in the subarray [33, 4]
rangeFreqQuery.query(0, 11, 33); // return 2. The value 33 occurs 2 times in the whole array.


&nbsp;
Constraints:


	1 &lt;= arr.length &lt;= 105
	1 &lt;= arr[i], value &lt;= 104
	0 &lt;= left &lt;= right &lt; arr.length
	At most 105 calls will be made to query


class RangeFreqQuery:
    def __init__(self, arr: List[int]):
        self.l = [[] for _ in range(10001)]
        for i, v in enumerate(arr):
            self.l[v].append(i)
    def query(self, left: int, right: int, v: int) -> int:
        return bisect_right(self.l[v], right) - bisect_left(self.l[v], left)
class RangeFreqQuery {
    //Use map's key to store arr's value, map's value to keep <value's location, cummulative arr's value count>
    HashMap<Integer, TreeMap<Integer, Integer>> map;
    public RangeFreqQuery(int[] arr) {
        //O(nlog(n))
        map = new HashMap<>();
        for(int i = 0; i < arr.length; i++){
            map.putIfAbsent(arr[i], new TreeMap<>());
            TreeMap<Integer, Integer> tree = map.get(arr[i]);
            //i = value's location
            //tree.size() = cummulative arr's value count - 1
            tree.put(i, tree.size());
        }
    }
    
    public int query(int left, int right, int value) {
        //O(log(n))
        
        //check if value exist in map
        if(!map.containsKey(value)){
            return 0;
        }
        TreeMap<Integer, Integer> tree = map.get(value);
        
        //check if there exist position >= left and position <= right
        //if not, return 0
        if(tree.ceilingKey(left) == null || tree.floorKey(right) == null){
            return 0;
        }
        //get leftMost position's cummulative count
        int leftMost = tree.get(tree.ceilingKey(left));
        //get rightMost position's cummulative count
        int rightMost = tree.get(tree.floorKey(right));
        
        return rightMost - leftMost + 1;
    }
}

/**
 * Your RangeFreqQuery object will be instantiated and called as such:
 * RangeFreqQuery obj = new RangeFreqQuery(arr);
 * int param_1 = obj.query(left,right,value);
 */
class RangeFreqQuery {
private:
    int size;
    unordered_map< int, vector<int> > mp;
public:
    RangeFreqQuery(vector<int>& arr) {
        size=arr.size();
        for (int i=0; i<size;i++){
            mp[arr[i]].push_back(i);
        }
    }
    int query(int left, int right, int value) {
        int first = lower_bound(mp[value].begin(),mp[value].end(),left)- mp[value].begin();
        int second = upper_bound(mp[value].begin(),mp[value].end(),right)- mp[value].begin();
        return second-first;
    }
};
 var RangeFreqQuery = function(arr) {

    this.array = arr;
    this.subRangeSize = Math.sqrt(this.array.length) >> 0;
    this.subRangeFreqs = [];

    let freq = {};

    for(let i = 0; i < arr.length; i++) {

        const num = arr[i];
    
        if(i >= this.subRangeSize && i % this.subRangeSize === 0) {
            this.subRangeFreqs.push({...freq});
            freq = {};
        }
        
        freq[num] = (freq[num] || 0) + 1;        
    }

    this.subRangeFreqs.push(freq);

};

RangeFreqQuery.prototype.query = function(left, right, value) {

    let fr = 0;

    const leftIdx = left / this.subRangeSize >> 0, rightIdx = right / this.subRangeSize >> 0;

    for(let i = leftIdx; i <= rightIdx; i++) {
        fr += this.subRangeFreqs[i][value] || 0;
    }

    for(let i = leftIdx * this.subRangeSize; i < left; i++) {
        fr -= this.array[i] === value ? 1 : 0;
    }

    for(let i = right + 1; i < Math.min((rightIdx + 1) * this.subRangeSize, this.array.length); i++) {
        fr -= this.array[i] === value ? 1 : 0;
    }
    return fr;
};
Range Frequency Queries