tvan's blog

Binary search on segment trees starting at any position? (in O (log n ))
By tvan, history, 4 years ago, In English

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 !

  • Vote: I like it
  • +31
  • Vote: I do not like it

Comments Comments (16)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +29 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      It is an O(n) memory RMQ.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Thanks for the link, did not know that

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Secondthread has also made a video on this.

          → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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.

      → Reply
»
4 years ago, # |
  Vote: I like it +65 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

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

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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

template<typename Acc, typename Pred>
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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply