### tvan's blog

By tvan, history, 7 weeks ago,

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.

• +31

 » 7 weeks ago, # | ← Rev. 2 →   +6 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
•  » » 7 weeks ago, # ^ |   +5 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.
•  » » » 7 weeks ago, # ^ |   0 by contiguous subsequence you mean subarray right?
•  » » » » 7 weeks ago, # ^ |   0 Yes, I forgot its English name
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   0 can you give a link to the problem?
•  » » » » 7 weeks ago, # ^ |   0 It is in Romanian, but this is the link.
 » 7 weeks ago, # | ← Rev. 2 →   +29 Binary search with RMQ in O(1) with O(n) memory (https://codeforces.com/blog/entry/78931) or two pointers if you want to query all the positions.
•  » » 7 weeks ago, # ^ |   0 RMQ doesn't fit the memory limits. What do you mean by two pointers?
•  » » » 7 weeks ago, # ^ |   +3 It is an O(n) memory RMQ.
•  » » » » 7 weeks ago, # ^ |   +10 Thanks for the link, did not know that
•  » » » » » 7 weeks ago, # ^ |   0 Secondthread has also made a video on this.
•  » » » 7 weeks ago, # ^ |   +5 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.
 » 7 weeks ago, # |   +65 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.
•  » » 7 weeks ago, # ^ |   +11 Thanks a lot for the idea, that's exactly what I was looking for.
 » 7 weeks ago, # | ← Rev. 2 →   +8 I'd imagine some implementation that looks like this (I tried to write it as generic as possible): template int search(int node, int b, int e, int l, int r, Acc& acc, Pred&& pred) { if (e <= l) return -1; if (b >= r) return b; if (b >= l && e <= r && pred(acc + T[node]) == 0) { acc = acc + T[node]; return -1; } if (b + 1 == e) return b; int m = (b + e) / 2; int res = search(node * 2, b, m, l, r, acc, pred); if (res != -1) return res; return search(node * 2 + 1, m, e, l, r, acc, pred); } 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.
 » 6 weeks ago, # |   0 Another elegant option is to use the binary lifting in $O(n)$ memory and $O(log(n))$ query described in this article.