线段树 - 在树的每一层最多访问 4 个顶点
Segment Tree - visiting at most 4 vertices at every level of the tree
在一条线段树中每层最多访问 4 个节点这一事实背后的证据或解释是什么？
除根级外，每一级最多可访问两个相邻段。因为如果要访问更多节点，它们中的一些将被合并到上层的一个段中（该节点将被访问而其子节点不会被访问，因为它的段将适合）。那么，最多可以有 2 组不相邻的线段，所以我们得到 2 * 2 是 4。最多可以有 2 组，因为我们可以在中间得到一个线段，然后在它的边上增加 2 个，并且比不再。之后到 right/left 的段只需要分别到 right/left 的其他较低级别的段。
我稍微画了一下，以便您更好地理解它。
The link to the seg tree image
在一条线段树中每层最多访问 4 个节点这一事实背后的证据或解释是什么？
除根级外，每一级最多可访问两个相邻段。因为如果要访问更多节点，它们中的一些将被合并到上层的一个段中（该节点将被访问而其子节点不会被访问，因为它的段将适合）。那么，最多可以有 2 组不相邻的线段，所以我们得到 2 * 2 是 4。最多可以有 2 组，因为我们可以在中间得到一个线段，然后在它的边上增加 2 个，并且比不再。之后到 right/left 的段只需要分别到 right/left 的其他较低级别的段。
我稍微画了一下，以便您更好地理解它。 The link to the seg tree image