kkogoro

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

线段树的空间分配

线段树的空间分配

普通写法

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

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

动态开点线段树

区间线段树

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

值域线段树

未离散化:需要开叶子节点个数*log(值域)大小(不是严格的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(值域)大小。但是,这个 $\log$ 不是严格的 $\log$ ,真正的深度可能会比 $\log$ 大,因此我们开的空间为叶子节点个数比log(值域)大一点的数 ,在具体实现上,我们可以将最大值域带入下面的程序来得到最深的深度,用叶子节点个数*最深深度作为空间大小。

int build(int l, int r, int cost) {
    if (l == r) return cost;
    int mid = (l + r) >> 1;
    return std::max(build(l, mid, cost + 1), build(mid + 1, r, cost + 1));
}
Last modification:January 17th, 2019 at 01:00 pm

Leave a Comment