Description
Design a data structure to answer range frequency queries. For each query, return the frequency of a value in a given subarray.
Examples
Input:
arr = [12,33,4,56,22,2,34,33,22,12,34,56], [[1,2,4],[0,11,33]]Output:
[1,2]Explanation:
Frequency in ranges.
Input:
arr = [12,33,4,56,22,2,34,33,22,12,34,56], [[1]]Output:
[1]Explanation:
Minimal case with a single query.
Input:
arr = [5,1,3,1,5,3,1,5], [[2,6,1],[0,7,5],[1,4,3]]Output:
[2,3,1]Explanation:
For each query [start, end, target]: Query 1 counts occurrences of 1 in range [2,6] which contains [3,1,5,3,1], so 1 appears 2 times. Query 2 counts occurrences of 5 in range [0,7] (entire array), so 5 appears 3 times. Query 3 counts occurrences of 3 in range [1,4] which contains [1,3,1,5], so 3 appears 1 time.
Constraints
- •
1 ≤ arr.length ≤ 10⁵