tree - Segment Tree - 在树的每一层访问最多 4 个顶点

Question

在段树中每个级别最多访问 4 个节点这一事实背后的证据或解释是什么？

标签： treenodeslevelssegment-treevisited

Answer 1

在除根层之外的每一层上，最多可以访问两个相邻的段。因为如果要访问更多，它们中的一些将在更高级别上合并为一个段（该节点将被访问而其子节点不会，因为它的段适合）。比，最多可以有 2 组不相邻的段，所以我们得到 2 * 2 是 4。最多可以有 2 组，因为我们可以在中间得到一个段，在它的边上得到 2 个加法，并且比不再。之后，右/左的段将只需要分别在右/左的其他较低级别的段。

我画了一点，以便您更好地理解它。 seg树图像的链接