线段树 O(logn) 最坏情况下的范围和如何？不应该是O(n)吗？如果在范围求和运算中，按照算法遍历左右节点会怎样？
最佳答案
我们将 active 节点称为存储区间的节点，该区间既不完全包含在区间中也不完全被区间覆盖。很容易发现，每个级别上最多有 2 个事件节点用于遍历。现在，如果一个节点不活跃，你不需要在其中递归——如果区间被完全覆盖，添加节点中写入的值，如果区间不与我们感兴趣的区间相交，只需跳过它。因此，算法将执行的操作数将按树的级别或 O(log(n)) 的顺序排列。
关于algorithm - 线段树的最坏情况运行时间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26905396/