2

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

4

3 回答 3

3

查询区间(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)

因此我们结束证明。

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

于 2015-06-28T05:42:28.627 回答
1

使用段树的范围查询基本上涉及从根节点递归。您可以将整个递归过程视为对段树的遍历：任何时候需要对子节点进行递归，您都是在遍历中访问该子节点。因此，分析范围查询的复杂性相当于找到访问的节点总数的上限。

事实证明，在任意级别，最多可以访问 4 个节点。由于段树的高度为 log(n)，并且在任何级别上最多可以访问 4 个节点，因此上限实际上是 4*log(n)。因此时间复杂度为 O(log(n))。

现在我们可以用归纳法证明这一点。基本情况位于根节点所在的第一级。由于根节点最多有两个子节点，所以我们最多只能访问这两个子节点，也就是最多4个节点。

现在假设在任意级别（例如级别 i）我们最多访问 4 个节点是真的。我们想表明我们将在下一个级别（第 i+1 级）最多访问 4 个节点。如果我们只访问了级别 i 的 1 或 2 个节点，那么很容易证明在级别 i+1 我们将访问最多 4 个节点，因为每个节点最多可以有 2 个子节点。

所以让我们专注于假设在第 i 层访问了 3 或 4 个节点，并尝试证明在第 i+1 层我们最多也可以有 4 个访问节点。现在因为范围查询要求一个连续的range，我们知道在级别 i 访问的 3 或 4 个节点可以分为 3 个节点分区：最左侧的单个节点，其段范围仅部分被查询范围覆盖，最右侧的单个节点，其段范围仅被部分覆盖由查询范围，以及 1 或 2 个段范围完全被查询范围覆盖的中间节点。由于中间节点的段范围完全被查询范围覆盖，因此在下一级不会有递归；我们只使用他们预先计算的总和。我们在最左边的节点和下一层的最右边的节点上留下了可能的递归，显然最多为 4 个。

这样就完成了归纳证明。我们已经证明，在任何级别上最多访问 4 个节点。因此，范围查询的时间复杂度为 O(log(n))。

于 2019-04-16T08:53:29.607 回答
0

长度为 n 的区间可以由 k 个节点表示，其中 k <= log(n)

我们可以根据二进制系统的工作原理来证明它。

于 2020-11-05T22:35:49.417 回答