1
$\begingroup$

We are given $k$ segments $(s_1,e_1),(s_2,e_2),(s_3,e_4),...,(s_k,e_k)$ where $s_i\le e_i$. Now we are given a query interval $[L,R]$ to find the largest segment $(s_i,e_i)$ contained within $[L,R]$.

By the term largest we mean among all the segments contained within $[L,R]$ return the one whose $e_i-s_i$ is maximum.

And by term contained we mean $L\le s_i\le e_i\le R$

I am looking for an approach to answer the query in $O(\log n)$ where $n = \max(R_i)-min(L_i)$

after some precomputation/tree-building etc costing no more than $O(k~\log n)$. So if I have to answer $q$ such queries my overall complexity should be $O(k~\log n\ +\ q~\log n)$.

All the above values are integers.

My thoughts:

Note that overall complexity I require is for online query ie lets just focus on solving for one query for now. For offline queries I found a solution here There it's mentioned that it can be solved for online too using Fractional cascading but doesn't quite explain it in detail.

The other related problem where I am trying to draw ideas from is this. For anyone who thinks they have something in mind please do refer these two resources.

$\endgroup$
8
  • $\begingroup$ Have you looked at segment trees? interval trees? $\endgroup$
    – D.W.
    Commented Aug 16, 2022 at 19:40
  • $\begingroup$ @D.W.Yes i am expecting a segment tree solution. Can you add it to the tags if you have privilege. $\endgroup$ Commented Aug 17, 2022 at 0:13
  • $\begingroup$ Is it possible to answer the query in $O(\log k)$? $\endgroup$
    – John L.
    Commented Aug 17, 2022 at 0:32
  • $\begingroup$ @JohnL. it should be but overall complexity should be $O(n\ log\ n)$ or $O(k\ log\ n)$ . I think it will need Lazy propagation with segment tree. $\endgroup$ Commented Aug 17, 2022 at 0:40
  • 1
    $\begingroup$ Although it doesn't meet your time requirements, your problem can be easily solved using range trees if you are willing to pay a preprocessing time of $O(k \log^2 k)$ and a query time of $O(\log^2 k)$. $\endgroup$
    – Steven
    Commented Aug 17, 2022 at 10:20

1 Answer 1

1
$\begingroup$

Your problem can be solved in $O(\log k)$ time per query by augmenting layered range trees. Let me start with a slower solution first, and then I discuss how the time complexity can be improved.

Consider each segment $[s_i, e_i]$ as a $2$-dimensional point $(s_i, e_i)$ with an associated weight $w_i$. In your case $w_i = e_i - s_i$, but the following solution works in general.

A 2D-range tree consists in a logarithmic-height outer binary-search tree in which each leaf represents the $x$-coordinate of a point, which can be thought of as a trivial interval. Each internal vertex $v$ having $u$ and $z$ as children represents the interval of the $x$-axis going from the left endpoint of $u$'s interval to the right endpoint of $v$'s interval.

A vertex $v$ of the outer tree points to an array $A(v)$ storing exactly the points whose $x$-coordinate lies in $v$'s interval. This array is sorted according to the points' $y$-coordinate.

Let $k$ be the number of points in the range tree. Given an interval $[x_a,x_b]$ of the $x$-axis and an interval $[y_a, y_b]$ of the $y$-axis, we can navigate the outer tree to find a set $V$ of $O(\log k)$ vertices such the union of their intervals covers exactly $[x_a,x_b]$. In your case $x_a = y_a = L$, $x_b = y_B = R$.

For each vertex $v \in V$ we can further binary search the array $A(v)$ to find the range of indices $i_v, j_v$ of $A(v)$ containing the points that simultaneously have their $x$ coordinate in $[x_a,x_b]$ (from the choice of $v$) and their $y$ coordinate in $[y_a, y_b]$ (from the binary search). Each binary search requires $O(\log k)$ time. Therefore, the total time spent so far is $O(\log^2 k)$.

To find the point with the largest weight, the trivial solution would be to inspect all points $(s_i,e_i)$ in the discovered ranges and return the one maximizing $w_i$, however this would be too costly since there can be many candidates. Instead, we can build a satellite range minimum query (RMQ) oracle $\mathcal{O}(v)$ attached to each $A(v)$. A range minimum query oracle preprocesses an array $B$ and, given two indices $i$ and $j$, is able to report an index $h$ such that $i \le h \le j$ and $B[h]$ is maximized. These oracles can be built in linear time and support constant-time queries. For each $A(v)$ consider the array $B(v)$ such that the $i$-th entry of $B(v)$ is the weight of the $i$-th point in $A(v)$ and then build a RMQ oracle $\mathcal{O}(v)$ on $B(v)$.

You can now query each oracle $\mathcal{O}(v)$ with $v \in V$ using the indices $i_v, j_v$ to find the point with maximum weight. Querying all oracles requires $O(\log k)$ time, and hence the overall time spent is $O(\log^2 k + \log k) = O(\log^2 k)$ per query.

To reduce the query time further, you can use the cross linking idea from fractional cascading. This is a known technique and the resulting data structure is known a layered range tree. Essentially, you are able to simultaneously find the set $V$ and, for each $v \in V$, all the indices $i_v$ and $j_v$ in time $O(\log k)$ (instead of $O(\log^2 k)$). This brings down the overall time needed to answer a query to just $O(\log k)$.

The building time of a layered range tree with two dimensions and $k$ points is $O(k \log k)$, and so is the time needed to build the satellite RMQ oracles (since the overall size of all the arrays is also $O(k \log k)$).


Here is a C++ implementation of a 2D Layered range tree that can be augmented by defining custom node types via dependency injection. The relevant file is TwoDLayeredRangeTree.h and is heavily commented.

In the same repository there is an implementation of a RMQ oracle via jump pointers. The building time of such an oracle is $O(n \log n)$ (more complex oracles having a linear building time exist) and the query time is $O(1)$ as long as std::bit_width runs in constant time (modern processors can report the number of leading 0s in a single instruction).

Finally, there is also an an example program defining a custom range tree node that uses the above RMQ oracle and (essentially) solves the problem mentioned above (more precisely it shows how to find the lightest point in a specified 2D query range).

A compiler supporting C++20 is required.

$\endgroup$
3
  • 1
    $\begingroup$ It would be great if there is a sample implementation in Python or C/C++. $\endgroup$
    – John L.
    Commented Aug 20, 2022 at 4:19
  • $\begingroup$ Boost's icl library is supposed to have all nlog n trees. If not from scratch should it be easier to implement using boost's ICL? boost.org/doc/libs/1_68_0/libs/icl/doc/html/index.html $\endgroup$ Commented Aug 21, 2022 at 8:27
  • $\begingroup$ @JohnL. See the updated answer :) $\endgroup$
    – Steven
    Commented Aug 25, 2022 at 21:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.