All problems
Segment Tree Merge Sort Tree Count
Problem
Count values less than or equal to x inside a range using a merge sort tree.
nums is the array. queries is a list of ["count", l, r, x] and each answer is how many elements in the inclusive range are at most x. Every tree node stores its segment sorted, and a query binary-searches each fully covered node.
Return the list of counts.
Hint
bisect_right on the sorted node lists counts values at most x.
Test cases
case 1
in: [[5,2,6,1],[["count",0,3,4]]]
expected: [2]
case 2
in: [[1,3,5,7],[["count",1,2,6],["count",0,0,0]]]
expected: [2,0]
case 3
in: [[2,2,2],[["count",0,2,2]]]
expected: [3]
case 4
in: [[],[]]
expected: []
case 5
in: [[4],[["count",0,0,5]]]
expected: [1]
Starter codePython
def merge_sort_tree_count(nums, queries):
# Your code here
pass5 test cases · run your code against them in the editor