Блог пользователя tvan

Автор tvan, история, 4 года назад, По-английски

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 !

  • Проголосовать: нравится
  • +31
  • Проголосовать: не нравится

»
4 года назад, # |
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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +29 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится +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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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