Range Frequency Queries
Problem
Design a class RangeFreqQuery built from an integer array arr. It must answer many calls of the form query(left, right, value), where each call returns how many times value appears in the subarray arr[left..right] (both ends inclusive). The array never changes, so the work should be done up front and each query should be fast.
arr = [12, 33, 4, 56, 22, 2, 34, 33, 22, 12], query(0, 9, 33)2from bisect import bisect_left, bisect_right
class RangeFreqQuery:
def __init__(self, arr):
self.pos = {}
for i, x in enumerate(arr):
self.pos.setdefault(x, []).append(i)
def query(self, left, right, value):
idx = self.pos.get(value)
if not idx:
return 0
lo = bisect_left(idx, left)
hi = bisect_right(idx, right)
return hi - lo// first index in sorted a with a[i] >= target
function lowerBound(a, target) {
let lo = 0, hi = a.length;
while (lo < hi) { const mid = (lo + hi) >> 1; if (a[mid] < target) lo = mid + 1; else hi = mid; }
return lo;
}
// first index in sorted a with a[i] > target
function upperBound(a, target) {
let lo = 0, hi = a.length;
while (lo < hi) { const mid = (lo + hi) >> 1; if (a[mid] <= target) lo = mid + 1; else hi = mid; }
return lo;
}
class RangeFreqQuery {
constructor(arr) {
this.pos = new Map();
for (let i = 0; i < arr.length; i++) {
if (!this.pos.has(arr[i])) this.pos.set(arr[i], []);
this.pos.get(arr[i]).push(i);
}
}
query(left, right, value) {
const idx = this.pos.get(value) || [];
const lo = lowerBound(idx, left);
const hi = upperBound(idx, right);
return hi - lo;
}
}class RangeFreqQuery {
Map<Integer, List<Integer>> pos = new HashMap<>();
public RangeFreqQuery(int[] arr) {
for (int i = 0; i < arr.length; i++)
pos.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
}
public int query(int left, int right, int value) {
List<Integer> idx = pos.getOrDefault(value, new ArrayList<>());
int lo = lowerBound(idx, left);
int hi = upperBound(idx, right);
return hi - lo;
}
// first index in sorted a with a.get(i) >= target
private int lowerBound(List<Integer> a, int target) {
int lo = 0, hi = a.size();
while (lo < hi) { int mid = (lo + hi) >>> 1; if (a.get(mid) < target) lo = mid + 1; else hi = mid; }
return lo;
}
// first index in sorted a with a.get(i) > target
private int upperBound(List<Integer> a, int target) {
int lo = 0, hi = a.size();
while (lo < hi) { int mid = (lo + hi) >>> 1; if (a.get(mid) <= target) lo = mid + 1; else hi = mid; }
return lo;
}
}class RangeFreqQuery {
unordered_map<int, vector<int>> pos;
public:
RangeFreqQuery(vector<int>& arr) {
for (int i = 0; i < (int)arr.size(); i++)
pos[arr[i]].push_back(i);
}
int query(int left, int right, int value) {
auto& idx = pos[value];
int lo = lower_bound(idx.begin(), idx.end(), left) - idx.begin();
int hi = upper_bound(idx.begin(), idx.end(), right) - idx.begin();
return hi - lo;
}
};Explanation
A naive query would scan from left to right and count matches, which costs O(n) every time. With many queries that is too slow, so we do all the heavy lifting once in the constructor.
For each value in the array we remember the sorted list of indices where it shows up. We build this with a single pass: walk the array left to right and append each index i to the bucket for arr[i]. Because we visit positions in order, every bucket comes out already sorted.
Now a query for value in range [left, right] is just: how many entries of that value's index list fall between left and right? Since the list is sorted, two binary searches pin down the window. lowerBound(left) gives the first index that is >= left, and upperBound(right) gives the first index that is > right. The gap between those two positions is the count.
Example: arr = [12, 33, 4, 56, 22, 2, 34, 33, 22, 12]. The value 33 has index list [1, 7]. For query(0, 9, 33), lowerBound(0) lands at position 0 and upperBound(9) lands at position 2, so the answer is 2 - 0 = 2.
If the value never appears, its bucket is empty (or missing), and the count is 0. Each query then costs only O(log k), where k is how often that value occurs.