Search code examples
algorithmsegment-tree

Segment tree: amount of numbers smaller than x

I'm trying to solve this problem.

I found tutorial for this problem but I don't get how to build segment tree that will find amount of numbers less than x in O(log n) (x can change). In tutorial it has been omitted.

Can anyone explain me how to do it ?

Solution

  • It is pretty simple:

    1. Store a sorted array of all numbers in a range covered by a particular node
      ( O(n * log n) memory and time for initialization).

    2. To answer a query, decompose the query segment into O(log n) nodes(the same way as it is done for a standard min/max/sum segment tree) and run binary search over the array stored in each of those nodes to find the number of elements less than x. It gives O(log^2 n) time per query. You can also achieve O(log n) using fractional cascading, but it is not necessary.