Segment Tree question

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
[Iasi] georgepopoiu
New poster
Posts: 3
Joined: Thu Aug 07, 2014 12:47 pm

Segment Tree question

Post by [Iasi] georgepopoiu » Wed Oct 08, 2014 7:55 am

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 !

MMMMMua.....
New poster
Posts: 1
Joined: Sat Jan 24, 2015 9:55 am

Re: Segment Tree question

Post by MMMMMua..... » Sat Jan 24, 2015 10:05 am

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.....

Post Reply

Return to “Algorithms”