data-structures - 段树时间复杂度分析

Question

我们如何证明分段树(http://letuskode.blogspot.in/2013/01/segtrees.html)(不要与间隔树相混淆)上的update和query操作是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。