kkogoro

线段树的空间分配
线段树的空间分配普通写法指通过 $idx<<1$ 来访问左子节点, $idx << 1 |...
扫描右侧二维码阅读全文
27
2018/11

线段树的空间分配

线段树的空间分配

普通写法

指通过 $idx<<1$ 来访问左子节点, $idx << 1 | 1$ 来访问右子节点的线段树写法

需要开叶子节点个数的4倍大小

动态开点线段树

区间线段树

需要开叶子节点个数的2倍大小

值域线段树

未离散化:需要开叶子节点个数*log(值域)大小

离散化后:需要开叶子节点个数的2倍大小

总结

值域较小

假设线段树维护的值域内的每个值都被插过入了(节点满了),本质就是 $2^{0}+2^{1}+2^{2}+...+2^{\log_{2}{n}}$

这是一个公比为2的等比数列求和,注意最后一项是第 $(\log_{2}{n})+1$ 项,带入求和公式得

$$ \frac{2^{0}\times (1-2^{(\log_{2}{n})+1})}{1-2}=2\times n $$

我们用这个方法来计算得到的答案就是叶子节点个数的2倍大小

值域较大

如果维护的值域特别大,插入的数的个数远远小于值域大小,我们假设每次插入的值互不相同,则每插入一个值到叶子节点约需要log(值域)个节点(线段树深度),我们用这个方法来计算得到的答案就是叶子节点个数*log(值域)大小

Last modification:November 27th, 2018 at 04:39 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment