段树时间复杂度分析

Question

我们怎样才能证明update和query操作上段树(http://letuskode.blogspot.in/2013/01/segtrees.html)(不要与间隔树混淆)是O(log n)？

我想到了一种这样的方式 - 在每个节点,我们在左右子树上最多进行两次递归调用.如果我们能够证明其中一个呼叫相当快地终止,那么时间复杂度将以对数为界.但是我们如何证明这一点呢？

Answer 1

引理:在树的每个级别最多使用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总共使用.

Answer 2

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

\n\n

\n\n

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

\n