段树-查询复杂度 [英] Segment tree - query complexity

问题描述

我在理解段树复杂性方面遇到问题.显然，如果您具有仅需更改一个节点的更新功能，则其复杂度将为log(n). 但是我不知道为什么查询(a，b)的复杂度是log(n)，其中(a，b)是需要检查的间隔. 谁能为我提供直观/正式的证明来理解这一点?

I am having problems with understanding segment tree complexity. It is clear that if you have update function which has to change only one node, its complexity will be log(n). But I have no idea why complexity of query(a,b), where (a,b) is interval that needs to be checked, is log(n). Can anyone provide me with intuitive / formal proof to understand this?

推荐答案

查询间隔(x，y)有四种情况

There are four cases when query the interval (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).

Intuitively, first three cases reduce the level of tree height by 1, since the tree has height log n, if only first three cases happen, the running time is 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.middle，则为案例1.如果x< = R.leftChild，那么我们将调用

For the last case, FIND() divide the problem into two subproblems. However, we assert that this can only happen at most once. After we called FIND(R.leftChild, x, R.middle), we are querying R.leftChild for the interval [x, R.middle]. R.middle is the same as R.leftChild.last. If x > R.leftChild.middle, then it is Case 1; if x <= R.leftChild, then we will call

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) )解决的时间.

However, the second FIND() returns R.leftChild.rightChild.sum and therefore takes constant time, and the problem will not be separate into two subproblems (strictly speaking, the problem is separated, though one subproblem takes O(1) time to solve).

由于对R的rightChild进行了相同的分析，因此我们得出结论，在case4首次发生之后，运行时间T(h)(h是树的剩余层)将为

Since the same analysis holds on the rightChild of R, we conclude that after case4 happens the first time, the running time T(h) (h is the remaining level of the tree) would be

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)

因此，我们结束证明.

这是我第一次做出贡献，因此，如果有任何问题，请指出来，我将编辑我的答案.

This is my first time to contribute, hence if there are any problems, please kindly point them out and I would edit my answer.

这篇关于段树-查询复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！