Wavelet Matrix Rank

Problem

Answer value-occurrence queries with a wavelet matrix.

nums holds small non-negative values (up to 4 bits) and queries is a list of ["count", l, r, x] asking how many times x appears in nums[l..r] inclusive. The wavelet matrix routes values through stable bit partitions so each query costs O(bits).

Return the counts in query order.

Hint

Counting values below x plus one minus values below x isolates the occurrences of x.

Test cases

case 1

in: [[1,4,2,4,3],[["count",0,4,4]]]

expected: [2]

case 2

in: [[1,4,2,4,3],[["count",1,3,4]]]

expected: [2]

case 3

in: [[0,0,0],[["count",0,2,0]]]

expected: [3]

case 4

in: [[],[]]

expected: []

Starter codePython

def wavelet_rank(nums, queries):
    # Your code here
    pass

4 test cases · run your code against them in the editor