#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/wavelet-trees/range-frequency-hash-map-approach

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/wavelet-trees/range-frequency-hash-map-approach

Repovive

Range Frequency: Hash Map Approach - Wavelet Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Range Frequency: Hash Map Approach

Alternative solution

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.