I was going through a blog (https://cp-algorithms.com/data_structures/segment_tree.html )
It says something like -
The query function is also almost equivalent, only now the lower_bound function of the multiset function should be called instead (std::lower_bound only works in O(logn) time if used with random-access iterators).
I need some help, to clarify few doubts(might help others too) —
- How can I define multiset with random-access iterators in C++?
- Can we find the rank of an element using it?
- How is it different from "C++ STL: Policy based data structures"?
0) I think it's typo, cause std::lower_bound works in O(n) with multiset (std::lower_bound works in O(log n) himself).
1) You can't make multiset with random-access iterator. What you can do — you can use std::lower_bound with any other type of iterator as if it's random-access iterator. In that case, C++ will use implementation of random-access iterator functions with your iterator. For example, for forward iterator function yourData[n] is something like this:
~~~~~
iterator = yourData.begin();
for (int i = 0; i < n; i++)
{
iterator++;
}
~~~~~
Which will work in linear time, obviously. That's why std::lower_bound works in linear time — for going to the middle of your data, you need to make steps half of it's length.
2) Yes you can. But only in linear time.
3) That's pretty much why you need STL::Tree