What if union of disjoint sets results in universal set?

Can a specialized version of the disjoint-set data structure support union and find on a set of intervals in constant time?

• Specifically, is there a way to maintain disjoint intervals of integers from 1 to N, while being able to support the following operations in constant time? Union: Merge two adjacent intervals. Find: Determine which interval a specified integer is in.

• Answer:

  http://academiccommons.columbia.edu/download/fedora_content/download/ac:143186/CONTENT/cucs-473-89.pdf notes that there exists an amortized constant-time algorithm for the interval union-find algorithm that outperforms the standard amortized [math]\alpha(n)[/math] disjoint set algorithm. The paper notes that this algorithm works whenever the structure of the unions is known in advance. It, however, requires a random-access machine whereas the standard algorithm only requires a pointer machine. http://digitool.library.colostate.edu///exlibris/dtl/d3_1/apache_media/L2V4bGlicmlzL2R0bC9kM18xL2FwYWNoZV9tZWRpYS8xNjY3MDE=.pdf by Gabow and Tarjan describes the actual "static tree set union" algorithm. One point of interest is that, surprisingly, there are quite a few applications of this "slight but theoretically significant improvement." The details, however, are complicated and are left to the reader to examine :)