algorithm - 段树的最坏情况运行时间

Question

段树 O(logn) 最坏情况下的范围和如何？不应该是O(n)吗？如果在范围求和操作期间，我们按照算法遍历左右节点怎么办？

Answer 1

让我们将一个active节点称为一个节点，该节点存储一个既不完全包含在区间内也不完全被区间覆盖的区间。很容易发现，每个级别最多有 2 个活动节点用于遍历。现在，如果一个节点不活动，您不需要在其中递归 - 如果区间被完全覆盖，则添加写入节点的值，如果区间不与我们感兴趣的区间相交，则只需跳过它。因此，算法将执行的操作数将按照树的级别或O(log(n)).

Answer 2

在第一步中，您可能必须遍历左右节点，但在随后的每个步骤中，您只需遍历其中一个边。另一种看待它的方式是注意，如果你想找到sum(n, m)（假设这表示半开区间的总和[n, m)），我们可以将其计算为

sum(n, m) = sum(0, m) - sum(0, n)

你会注意到计算sum(0, n)和sum(0, m)每个都需要对数时间，因为你不需要双向遍历。例如，

sum(0, 13) = sum(0, 8) + sum(8, 12) + sum(12, 13)

其中右侧的每个术语都已存储在段树中。