Hello.

I have recently encountered a problem where I need to binary search on a segment tree starting at any position( there are no updates, but there isn't enough memory for a sparse table). The problem is that the time limit does not allow a O(logn ^2) binary search , so I'm wondering if there is a different approach. The segment tree is for maximums, so transforming the binary search by including the prefix then removing it is ( I think) not possible.

Thanks for your help !

I am assuming that you want to find the nearest max element. I also encountered a problem like this. Don't use segment trees. Use monotonic stack

Actually no, I'm looking to find the longest contiguous subsequence starting at a position for which max — min < S , where S is a constant. So a monotonic stack doesn't really help me.

by contiguous subsequence you mean subarray right?

Yes, I forgot its English name

can you give a link to the problem?

It is in Romanian, but this is the link.

Binary search with RMQ in O(1) with O(n) memory (https://mirror.codeforces.com/blog/entry/78931) or two pointers if you want to query all the positions.

RMQ doesn't fit the memory limits. What do you mean by two pointers?

It is an O(n) memory RMQ.

Thanks for the link, did not know that

Secondthread has also made a video on this.

I think he means trying to move the right pointer when it's possible and when max — min >= S, move the left pointer. You can maintain max and min by deque.

binary searching on segtree in general can be done without requiring the operation to be invertible.

when we query/update an interval

`[l, r)`

on the segment tree, the data structure split the interval into`O(log N)`

non-overlapping precalculated subintervals`[l_0 = l, r_0), [l_1 = r_0, r1), ..., [l_(k-1), r_(k-1) = r)`

, which is the reason it takes`O(log N)`

for those operations.So if you wanna binary search from a point

`p`

, just split the range`[p, N)`

into`O(log N)`

subintervals the same way. One of those subintervals`[s, t)`

must contain the desired answer. Find it by simply iterating over. Then just do prefix binary search on`[s, t)`

in the usual way you do it in the case where`p = 0`

.Thanks a lot for the idea, that's exactly what I was looking for.

I'd imagine some implementation that looks like this (I tried to write it as generic as possible):

The function would return the first index for which

`pred()`

returns $$$1$$$ or something.`acc`

would be some accumulated value over the range $$$[l..r]$$$ (say, for example, you want to find out minimum $$$r$$$ such that $$$gcd(a(l), a(l + 1), ..., a(r)) == 1$$$, what you would do is have $$$acc + T[node] = gcd(acc, T[node])$$$. If you want to search over some range bounded by $$$r$$$, you can just write some code that acts as if`pred()`

would have evaluated to true for nodes after $$$r$$$.I didn't test this implementation, so I wouldn't be surprised if I have some bug.

Ranges are half-open.

Another elegant option is to use the binary lifting in $$$O(n)$$$ memory and $$$O(log(n))$$$ query described in this article.