AnotherRound's blog

Answering queries of the type "longest interval contained in the given interval"
By AnotherRound, history, 5 years ago, In English

I recently asked a question on cs.stackexchange, but since I got no answers there, I figured I should ask here too :)

The problem is the following: We are given a set of intervals (if you want, make it empty in the beginning). Then we have $$$Q$$$ queries, which are of one of the following types:

  1. Add a new interval to the set
  2. For a given query interval $$$[l_i, r_i]$$$, find the length of the longest interval from the set which is contained entirely inside $$$[l_i, r_i]$$$.

As mentioned in the linked question, if we didn't have query type 1, we can do a persistent segment tree and handle the queries. I have also been thinking we can do SQRT decomposition and answer in $$$O(Q\sqrt Q)$$$. Is there a better algorithm? I would like to be able to do this in $$$O(Q \log Q)$$$ or $$$O(Q \log^2 Q)$$$

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

»
5 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Map update intervals to points $$$(L, R)$$$ on the plane with weight $$$R - L$$$. Queries are the maximum weight of a point in the square with corners $$$(L, L), (R, R)$$$. You can do polylog with any of your favorite data structures like 2D segtree, segtree of BBST and whatnot.

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

Online, $$$l_i, r_i \leq 10^9$$$:

Use a sparse segment tree with a sparse BIT in each node. In the segment tree, the node representing range $$$[L, R]$$$ contains all intervals $$$i$$$ such that $$$l_i \in [L, R]$$$. In the BIT, the value of the element at index $$$r_i$$$ is $$$r_i - l_i + 1$$$.

This reduces the problem to:

  1. Given an index $$$r$$$, find the maximum element in $$$[0, r]$$$.
  2. Given an index $$$r$$$ and value $$$v$$$, set the value of the element at index $$$r$$$ to $$$\max(value, v)$$$.

This is easily solvable with a BIT. Complexity: $$$O(Q \log^2 (10^9))$$$ with a high constant factor.

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

    how to implement a sparse binary indexed tree? do u have any code.

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

There exists a general offline approach, when you have inserts in a set and queries that are cumulative and you can easily solve the problem if all inserts were before the queries.

Lets say the operations are stored in an array $$$\mathtt{op[1\ldots Q]}$$$. Then use this divide and conquer approach -- 

solve(l, r): 
  if l == r: return
  m = (l + r) / 2
  inserts = inserts in op[l..m]
  queries = queries in op[m+1..r] 
  updateAnswer(inserts, queries) 
  solve(l, m)
  solve(m + 1, r)

If you call $$$\mathtt{solve(1, Q)}$$$, you'll see that for every query this divide and conquer approach will consider every updates before it. If the objective function is cumulative then updating answer for each chunk will result in correct answer.

In your problem, the $$$\mathtt{updateAnswer}$$$ part can be done by line sweep; by sorting both the inserts and the queries by one end point and keeping a Binary Indexed tree on the other end point. This will result in $$$O(Q\log Q)$$$ for each recursion depth. So in total $$$O(Q \log^2 Q)$$$.

For other uses of this approach see the sections of CDQ Divide and Conquer from this slide: https://assets.hkoi.org/training2018/dc.pdf

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

To get a single log, I remember keywords like fractional cascading and interval tree (not segment tree). Does somebody confirm that it's one of these two? :D

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

There is also a technique to expand a static queryable Data Structure in O(log n) Amortised Complexity per query. Just maintain a Static Data structure in sizes of 2^i. On adding, Keep merging into the smallest set unless all are again size of 2^i. Find the best on all log(n) sets separately. You can use any of the online/offline approaches of the second part with just a log(n) extra in the complexity.

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

Never mind

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

    I don't see why we can ignore intervals contained inside another intervals, because we might have a query which contains the smaller, but not the larger interval. Or do we reorder queries somehow?

    → Reply