Disjoint Sparse Table Range Minimum

Problem

Build a disjoint sparse table for static range-minimum queries. Pad nums to a power of two, and for each level k precompute suffix minima on the left half and prefix minima on the right half of every block of size 2^(k+1). A query [l, r] with l < r combines the two entries at the level of the highest bit where l and r differ; l == r returns nums[l]. Return the answers to queries in order, and [] for an empty array.

Hint

The highest differing bit of l and r picks the level whose block split separates them, so two lookup values cover [l, r].

Test cases

case 1

in: [[3,1,4,1,5,9,2,6],[[0,7],[1,4],[2,5],[0,3],[4,7],[2,2]]]

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

case 2

in: [[7,2,9],[[0,2],[0,0],[1,2],[2,2]]]

expected: [2,7,2,9]

case 3

in: [[5],[[0,0]]]

expected: [5]

case 4

in: [[],[]]

expected: []

Starter codePython

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

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