英文:
Proof that height of segment tree is ceil(log(n))
问题
我正在阅读关于这个 Quora 答案，关于段树所需的内存空间。在第二段中，作者假设段树的高度为ceil(log(n))，其中n是用于构建树的数组的大小。
经过几个示例后，我注意到每当n是2的幂时，段树的最后一层包含大小为1的段。当n超过这个2的幂时，该层上的一些大小为1的段会变成大小为2的段，根据上述高度公式，树的高度增加1。
但我似乎无法找到段树的高度是ceil(log(n))的严格证明。任何帮助将不胜感激。
英文:
I was reading up on this Quora answer on memory space required by segment trees. In the second paragraph, the author assumes that the height of a segment tree is ceil(log(n)), where n is the size of the array from which the tree is being formed.
After going through a few examples, I noticed that whenever n is a power of 2, the last level of the segment tree contains segments of size 1. Whenever n exceeds this power of 2, some segments of size 1 on this level become segments of size 2, increasing the height of the tree by 1, in accordance with the above formula for height.
But I can't seem to figure out a strict proof that the height of a segment tree is ceil(log(n)). Any help would be appreciated.
答案1
得分: 1
一个展示这一点的方法是证明以下内容：如果 n ≤ 2^k，则包含 n 个元素的数组的线段树的高度最多为 k。然后，由于 n = 2^lg n ≤ 2^⌈lg n⌉，我们得出 n 个节点的线段树的高度最多为 ⌈lg n⌉。
我们可以通过对 k 进行归纳来证明这个不等式成立。作为基本情况，仅当 n ≤ 2^0 时，即 n = 1 时，包含 n = 1 个项目的线段树只包含一个单一节点，其高度为 0。
对于归纳步骤，假设对于 k 成立。现在选择一个 n，其中 n ≤ 2^(k+1)。线段树由一个根节点和两个大小分别为 ⌊n/2⌋ 和 ⌈n/2⌉ 的子数组组成。你可以证明这两个数量都上界为 2^k（对于 ⌊n/2⌋ 来说很容易；对于 ⌈n/2⌉ 来说比看起来更复杂一些），因此我们可以应用归纳假设，得出这两个子数组的线段树的高度都不超过 k。将这与根节点结合起来，得到的线段树的高度最多为 k+1，这正是所需的。
英文:
One way to show this is to prove the following: if n ≤ 2<sup>k</sup>, then a segment tree for an array of n elements has height at most k. Then, since n = 2<sup>lg n</sup> ≤ 2<sup>⌈lg n⌉</sup>, we get that a segment tree for n nodes has height at most ⌈lg n⌉.
We can show that this inequality holds by induction on k. As a base case, the only n where n ≤ 2<sup>0</sup> is n = 1, and a segment tree for n = 1 items consists of just a single node, which has height 0.
For the inductive step, suppose the claim is true for k. Now pick an n where n ≤ 2<sup>k+1</sup>. The segment tree consists of a root node with two subarrays of sizes ⌊n/2⌋ and ⌈n/2⌉. You can show that both of these quantities are bounded from above by 2<sup>k</sup> (the floor case is easy; the ceiling case is a little more subtle than it looks), so we can apply the IH to get that the segment trees for those subarrays each have height at most k. Combining that with the root node gives a segment tree of height at most k+1, as needed.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论