我在与搜索树相关的算法和数据结构的理论作业中遇到了这个问题：
给定n个数a1an，最初每个都在自己的集合中。有两种类型的查询：
- 联合两个集合
- 在特定集合中找到大于x的最小元素
在这些查询中，set是由{ai}中的一个元素的索引指定的。任务是在O(n+q log(n((时间内处理q查询。
我尝试过使用AVL树来存储集合的元素，但这种方法会导致O(n log(n((或O(n(merge时间，因此无法满足总体时间复杂性要求。目前我只有这几个想法(但实际上它们并没有太大帮助(：
- 最多有n个联合查询
- 如果q>最终，我们需要构建一个包含{ai}的所有n元素的搜索树，以处理最后一个(q-n(类型的查询。因此，首先解决q≤n的问题，然后自然地将解扩展到q>n
- 要创建一个包含(k+1(元素的集合，至少需要k合并操作(这很容易通过数学归纳来证明(，因此在处理查询的每一步，我们都需要使用"；不那么大"；仅设置。这可能会产生一些严格的渐近估计
- 可能有一种方法可以在处理前扫描几个第一个查询，了解类型(2(查询中涉及哪些集合，并仅合并它们，忽略其他联合请求
- 没有内存限制，所以这可能在某种程度上被滥用
实际上，您使用自平衡二进制搜索树来表示集合的解决方案是正确的，并且您的想法(1(-(3(对于实现更严格的渐近界至关重要。
最初设置集合是O(n(，并且在每个集合内搜索(找到比一些x大的最小元素(是O(logn(，所以q搜索的代价是O(q-logn(。
现在让我们考虑合并操作。要合并大小为a和b的两个二进制搜索树，请将较小树的所有元素插入较大树中。这可以在O(min(a,b)*log(max(a,b)+1))中完成。
但是，如果我们从单例集开始，q个连续合并操作的复杂性是多少？我们可以通过归纳法证明，对于q<n、 成本为O(q-logn(。(正如您所指出的，除了将集合与自身合并之外，不能再进行任何合并操作，这是一个禁忌。(
因此，q合并操作的成本是q-1合并的成本加上最后一次合并的成本。根据归纳假设，q-1合并的成本为O((q-1)log n)。
最后一次合并的成本为O(min(a,b)*log(max(a,b)+1))。但是a和b小于q，所以对于最后一次合并，我们得到了O(q * log(q + 1))的上界。由于q < n，这是O(q log n)的子集。因此，q个合并操作的总成本是O((q-1) log n + q log n) = O(q log n)。
因此，总复杂度受O(n+q-logn(的限制。