Answer Repeated Range-Frequency Queries
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Implement a `RangeFreqQuery` object for a fixed integer array `arr`. Construct the object from the supplied array for later queries. Each call to `query(left, right, value)` returns the number of occurrences of `value` between zero-based indices `left` and `right`, including both endpoints. The array does not change after construction.
```cpp
class RangeFreqQuery {
public:
RangeFreqQuery(vector<int>& arr);
int query(int left, int right, int value);
};
```
### Examples
**Example 1:**
```text
arr = [4,7,4,4,9]
Calls: query(1,3,4), query(0,4,7)
Results: 2, 1
Explanation: Two 4s lie at indices 2 and 3; 7 occurs once overall.
```
**Example 2:**
```text
arr = [2,2]
Calls: query(0,0,2), query(0,1,3)
Results: 1, 0
Explanation: Inclusive single-index queries count that element, and absent values count zero.
```
### Constraints
- `1 <= arr.length <= 10^5`.
- Array entries and queried values lie in `[1,10^4]`.
- `0 <= left <= right < arr.length`; at most `10^5` queries.
### Clarifying Questions
Both endpoints are included. Queries do not update the array.
```hint Inspect the structure
Can all positions of one value be stored in increasing order during one pass?
```
### Reasoning checkpoints
- Count occurrences in the requested inclusive interval rather than in the entire array.
- Return zero for absent values and handle single-position queries.
- Support the full sequence of queries efficiently while preserving the constructor and query protocol.
### Optional extensions
What changes if point updates are added to the interface?
Overview: Answer Repeated Range-Frequency Queries. Implement the original persistent RangeFreqQuery class. Construct it from arr and answer query(left,right,value) with the number of occurrences of value in the inclusive zero-based subarray arr[left...right]. The array is fixed after construction.
