线段树-查询复杂度

Question

我在理解线段树复杂性方面遇到问题。很明显，如果你有一个只需要更改一个节点的更新函数，那么它的复杂度将为 log(n)。但我不知道为什么查询（a，b）的复杂性是log（n），其中（a，b）是需要检查的区间。谁能为我提供直观/正式的证据来理解这一点？

Answer 1

查询区间(x,y)有四种情况

FIND(R,x,y) //R is the node
% Case 1
    if R.first = x and R.last = y   
        return {R}
% Case 2
    if y <= R.middle
        return FIND(R.leftChild, x, y) 
% Case 3
    if x >= R.middle + 1 
        return FIND(R.rightChild, x, y) 
% Case 4
    P = FIND(R.leftChild, x, R.middle)
    Q = FIND(R.rightChild, R.middle + 1, y)    
    return P union Q.

直观上，前三种情况将树的高度降低了1级，因为树的高度为log n，如果只发生前三种情况，则运行时间为O(log n)。

对于最后一种情况，FIND() 将问题分为两个子问题。然而，我们断言这种情况最多只能发生一次。调用 FIND(R.leftChild, x, R.middle) 后，我们正在向 R.leftChild 查询区间 [x, R.middle]。R.middle 与 R.leftChild.last 相同。如果 x > R.leftChild.middle，则为情况 1；如果 x <= R.leftChild，那么我们将调用

FIND ( R.leftChild.leftChild, x, R.leftChild.middle );
FIND ( R.leftChild.rightChild, R.leftChild.middle + 1, , R.leftChild.last );

然而，第二个 FIND() 返回 R.leftChild.rightChild.sum ，因此需要常数时间，并且问题不会分成两个子问题（严格来说，问题是分离的，尽管一个子问题需要 O(1) 时间来解决）解决）。

由于同样的分析也适用于 R 的 rightChild，我们得出结论，case4 第一次发生后，运行时间 T(h)（h 是树的剩余级别）为

T(h) <= T(h-1) + c (c is a constant)
T(1) = c

产生：

T(h) <= c * h = O(h) = O(log n) (since h is the height of the tree)

至此我们结束证明。

这是我第一次投稿，如果有任何问题，请指出，我会编辑我的答案。