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:

- Add a new interval to the set
- 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)$$$

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.

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:

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

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

Just replace the Vector you keep with a unordered_map/map.

awesome .

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 --

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

Thanks, this seems a pretty cool technique!

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

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.

What do you mean by "merging into the smallest set unless .." ?

This

Thanks, I'll check this out.

What kind of data structure would be used for that second part?

Never mind

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?

Sr my bad. Misread it.