突然想到,满二叉树不是才2n-1个节点么,为什么开4倍空间??
因为线段树和二叉树是有一点区别的,线段树结点存的是区间,二叉树存的是点,所以线段树会出现许多结点空着的情况 见下图
所以,对于n个点,比n大的最小二次幂即为线段树最底层的结点数,所以所有结点数为 \[ 2^{\lfloor\log_2n\rfloor+1}*2-1 \]
即为4n
2024-03-13 09:05:27
突然想到,满二叉树不是才2n-1个节点么,为什么开4倍空间??
因为线段树和二叉树是有一点区别的,线段树结点存的是区间,二叉树存的是点,所以线段树会出现许多结点空着的情况 见下图
所以,对于n个点,比n大的最小二次幂即为线段树最底层的结点数,所以所有结点数为 \[ 2^{\lfloor\log_2n\rfloor+1}*2-1 \]
即为4n
下一篇:Catalan数