我在理解线段树的复杂性方面遇到了问题。很明显,如果你有只需要改变一个节点的更新函数,它的复杂度将是 log(n)。 但我不知道为什么查询(a,b)的复杂性是 log(n),其中(a,b)是需要检查的间隔。 任何人都可以为我提供直观/正式的证据来理解这一点吗?
最佳答案
查询区间(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,则为Case 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)
至此证明结束。
第一次投稿,如有问题请指出,我会修改答案。
关于time-complexity - 线段树——查询复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30236813/