我有理解线段树的复杂性问题。 很显然，如果你有这必须改变只有一个节点更新功能，它的复杂性会的log（n）。 但我不知道为什么查询的复杂性，需要进行检查（A，B），其中（A，B）为间隔，是的log（n）。 任何人都可以向我提供直观/正式证明理解？
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降低树高的水平，因为树有高度数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成立时，我们的结论是发生情形4在第一时间之后，运行时间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)
因此，我们最终证明。
这是我第一次做贡献，因此，如果有任何问题，请您指出来，我会编辑我的答案。
Answer 2:
使用段树中的范围查询基本上涉及从根节点递归。 你可以把整个递归过程为上段树遍历：需要一个子节点上的递归任何时候，你正在访问您遍历该子节点。 因此分析范围查询的复杂性等同于找到上限已访问节点的总数。
事实证明，在任意的水平，有可被访问最多4个节点。 由于该段树有日志（n）的高度，并且在任何级别的有在可访问最多4个节点，上限实际上是4 *的log（n）。 因此，时间复杂性为O（的log（n））。
现在我们可以归纳证明这一点。 基础案例是在其中根节点位于第一级。 因为根节点最多有两个子节点，我们只能访问最多的两个子节点，这是最多4个节点。
现在假设这是事实，在任意级别（说I级），我们参观最多4个节点。 我们要展示我们将在下一级别的访问最多4个节点（I级+ 1）为好。 如果我们访问了在一级我只有1或2个节点，是微不足道的表明，在I级+ 1，我们将访问最多4个节点，每一个节点最多只能有2个节点。
因此，让我们专注于3个或4个节点中的水平，我参观了假设，并尝试表明，在I级+ 1，我们还可以有最多4访问节点。 现在，由于该范围的查询是要求一个连续的范围中，我们知道，3个或4个节点访问在第i级可分为3个分区的节点：一个最左边的单个节点，其段范围仅部分由查询范围所覆盖，一最右边的单个节点，其段范围仅部分由查询范围覆盖，并且1个或2个中间节点，其段范围由查询范围完全覆盖。 由于中间节点有自己的网段范围内（一个或多个）由查询范围完全覆盖，就在一个新的水平没有递归; 我们只是用自己的预先计算的款项。 我们只剩下最左边的节点上可能递归和下一级最右边的节点，这显然是最多4。
这就完成感应的证明。 我们已经证明，在任何级别最多4个节点访问。 因此，对于一范围的查询的时间复杂度是O（的log（n））。
文章来源: Segment tree - query complexity
