Formatted question description: https://leetcode.ca/all/2080.html

# 2080. Range Frequency Queries (Medium)

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**).

**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]ExplanationRangeFreqQuery 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.

**Constraints:**

`1 <= arr.length <= 10`

^{5}`1 <= arr[i], value <= 10`

^{4}`0 <= left <= right < arr.length`

- At most
`10`

calls will be made to^{5}`query`

**Companies**:

Quora

**Related Topics**:

Array, Binary Search

## Solution 1. Binary Search

Initialization: For each unique value in `A`

, store its corresponding indices in a map `m`

.

Query:

- If
`value`

doesn’t exist in the original array, return`0`

. - Otherwise, let
`v = m[value]`

– the array of all the indices of`value`

in the original array - Let
`j`

be the first index that`v[j] > right`

. - Let
`i`

be the first index that`v[i] >= left`

. - The answer is
`j - i`

.

```
// OJ: https://leetcode.com/problems/range-frequency-queries/
// Time:
// RangeFreqQuery: O(N)
// query: O(log(N))
// Space: O(N)
class RangeFreqQuery {
unordered_map<int, vector<int>> m; // map from a value to all its indices
public:
RangeFreqQuery(vector<int>& A) {
for (int i = 0; i < A.size(); ++i) m[A[i]].push_back(i);
}
int query(int left, int right, int value) {
if (m.count(value) == 0) return 0; // `value` doesn't exist in the original array
auto &v = m[value]; // `v` is the array of all the indices of `value` in the original array
int j = upper_bound(begin(v), end(v), right) - begin(v); // Find the first index `j` that `v[j] > right`.
int i = lower_bound(begin(v), end(v), left) - begin(v); // Find the first index `i` that `v[i] >= left`.
return j - i; // The answer is `j - i`
}
};
```

## Discuss

https://leetcode.com/problems/range-frequency-queries/discuss/1589028/C%2B%2B-Straightforward-Binary-Search