Segment Tree Query Node Count

Problem

Count the canonical nodes used by a segment tree range query.

For n leaves, a query [l, r] decomposes into disjoint nodes whose segments are fully covered. Recurse as a segment tree would: a fully covered node contributes one, a disjoint node contributes zero, and a partial node splits.

Return the node count for each query.

Hint

A query decomposes into at most two nodes per level of the tree.

Test cases

case 1

in: [8,[[0,7],[0,0],[1,6],[2,5]]]

expected: [1,1,4,2]

case 2

in: [1,[[0,0]]]

expected: [1]

case 3

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

expected: [0]

case 4

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

expected: [1,3]

Starter codePython

def segtree_query_node_count(n, queries):
    # Your code here
    pass

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