Order-Statistic BST Rank Query

Problem

Insert values into a plain BST augmented with subtree sizes, following the given insertion order; duplicate values are ignored. For each query value x, return the 0-based rank, that is, the number of stored values strictly smaller than x, even when x itself is not stored. An empty insertion list makes every rank 0.

Hint

When x is larger than the current node, count the node plus its entire left subtree and descend right.

Test cases

case 1

in: [[5,3,8,1,4,7,9],[4,5,9,0,10]]

expected: [2,3,6,0,7]

case 2

in: [[2,2,3],[2,3,1]]

expected: [0,1,0]

case 3

in: [[],[1,2]]

expected: [0,0]

case 4

in: [[1,2,3,4,5],[5,4,3,2,1]]

expected: [4,3,2,1,0]

Starter codePython

def ost_rank_queries(values, queries):
    # Your code here
    pass

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