Wavelet Tree Range Count

Problem

Build a 4-bit wavelet tree over nums (values 0..15) and count values in a value range for a subarray. queries contains [l, r, lo, hi] and the answer is how many positions i with l <= i <= r satisfy lo <= nums[i] <= hi. Compute count_less(hi + 1) - count_less(lo) by routing through the bit levels using zero counts. Return the answers in order.

Hint

count_less sums the zeros in a range whenever the queried value turns a bit on, then follows the matching branch.

Test cases

case 1

in: [[1,5,3,7,2,9],[[0,2,1,5],[0,5,0,15],[3,3,7,7],[0,5,10,15]]]

expected: [3,6,1,0]

case 2

in: [[0,15,8,8,4],[[1,4,4,15],[0,0,0,0],[2,3,8,8]]]

expected: [4,1,2]

case 3

in: [[10],[[0,0,10,10],[0,0,0,9]]]

expected: [1,0]

Starter codePython

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

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