10

我们如何证明分段树 ( http://letuskode.blogspot.in/2013/01/segtrees.htmlupdate ) 上的andquery操作（不要与区间树混淆）是？O(log n)

我想到了一种方法——在每个节点上，我们最多对左右子树进行两次递归调用。如果我们能够证明其中一个调用相当快地终止，那么时间复杂度将是对数有界的。但我们如何证明这一点？

4

4 回答 4

12

引理：树的每一层最多使用 2 个节点（一层是与根有固定距离的节点的集合）。
证明：假设在该级别h至少使用了 3 个节点（我们称它们L为M和R）。这意味着从节点的左边界到L节点的右边界的整个区间都R在查询范围内。这就是为什么从完全位于查询范围内的级别M完全被一个节点（我们称之为它UP）覆盖的原因。h - 1但这意味着M根本无法访问，因为遍历将在UP节点或更高节点处停止。以下是一些图片来阐明证明的这一步： 

 h - 1:  UP          UP        UP
         /\          /\        /\
 h:     L  M R    L M  R    L  M   R

这就是为什么每个级别最多使用两个节点的原因。段树中只有log N级别，因此最多2 * log N总共使用。

于 2014-11-28T15:07:42.007 回答
5

声称在每个级别上最多扩展 2 个节点。我们将通过反证法来证明这一点。考虑下面给出的线段树。

在此处输入图像描述

假设在这棵树中展开了 3 个节点。这意味着范围是从最左边的彩色节点到最右边的彩色节点。但请注意，如果范围延伸到最右边的节点，则覆盖中间节点的整个范围。因此，该节点将立即返回该值并且不会被扩展。因此，我们证明在每个级别，我们最多扩展 2 个节点，并且由于有 log⁡n 级别，因此扩展的节点是 2⋅logn=Θ(logn)

于 2017-09-17T12:43:06.143 回答
1

如果我们证明在每个级别上最多有 N 个节点可以访问并且知道二叉树的最大 logN 高度 - 我们可以说查询操作的复杂度是 O(LogN)。其他答案告诉您，每个级别最多访问 2 个节点，但我假设最多访问 4 个节点，访问级别上的 4 个节点。您可以在Geek for Geeks等其他来源中找到相同的声明而无需证明

其他答案显示您的分段树太小。考虑这个例子：叶节点大小为 16 的分段树，索引从零开始。您正在寻找范围 [0-14] 参见示例：交叉是我们正在访问的节点 在此处输入图像描述

于 2019-12-01T16:22:29.010 回答
0

在树的每个级别 (L) 上，最多有 2 个可能有部分重叠的节点。（如果无法证明 - 为什么？，请提及）

因此，在级别 (L+1) 我们必须探索最多 4 个节点。树中的总高度/级别为 O(log(N))（其中 N 是节点数）。因此时间复杂度为 O(4*Log(N)) ~ O(Log(N))。

PS：请参考@Oleksandr Papchenko 所附的图表以获得更好的理解。

于 2020-10-04T05:54:44.230 回答