Clever Geek Handbook

Segment tree: number of numbers less than x

I am trying to solve this problem .

I found a tutorial for this problem, but I don't understand how to build a segment tree that will find the number of numbers less than x in O (log n) (x may change). It is omitted in the textbook.

Can someone explain to me how to do this?

+3


source to share


1 answer


It's pretty simple:



  • Store a sorted array of all numbers in the range covered by a specific node memory
    ( O(n * log n)

    and initialization time).

  • To answer the query, decompose the query segment into nodes O(log n)

    (just as you do for the standard min / max / sum tree) and do a binary search through the array stored in each of these nodes to find the number of elements less x

    . He gives time O(log^2 n)

    for each request. You can also achieve O(log n)

    with fractional cascading, but this is optional.

+4


source






More articles:


All Articles