Page 1 of 1

Segment Tree question

Posted: Wed Oct 08, 2014 7:55 am
by [Iasi] georgepopoiu
Hello, I recently remembered a problem statement that was something like this :

We have an array A of n integers and we need to answer the following type of queries. Q(l, r, p) means how many numbers from A[l..r] are less than p. The author mentioned that it can be done using a segment tree, but did not provide any further clarifications and I cannot wrap my head around it.

Any ideas/tips ?

Thanks in advance !

Re: Segment Tree question

Posted: Sat Jan 24, 2015 10:05 am
by MMMMMua.....
You have to build a segment tree in this way.
That is, for every segment tree node, it stored a sorted sequence of it's interval(use vector to allocate memory dynamically).
Obviously, the space complexity is O(nlogn).
And, for every query, use binary search to find out how many numbers are smaller than p, while locating the query interval(just like a normal segment tree).
So the time complexity is O(n(logn)^2).
I'm not an English speaker, so just ignore any grammer mistakes.....