Range Frequency: Hash Map Approach

For this specific problem, a hash map approach works:

class RangeFrequency:
    positions: map from value to list of indices

    function __init__(arr)
        for i from 0 to length - 1
            positions[arr[i]].append(i)

    function query(l, r, v)
        if v not in positions then
            return 0
        // Binary search for indices in [l, r]
        list := positions[v]
        left := lower_bound(list, l)
        right := upper_bound(list, r)
        return right - left

Time: $O(\log n)$ per query using binary search.

Space: $O(n)$.

This is simpler than wavelet tree for single-value frequency queries.