线段树

普通的写线段树的方法是

1
2
3
4
5
6
7
void build(int rt, int l, int r) {
      if (l != r)  {
          int m = l + r >> 1;
          build(rt + rt, l, m);
          build(rt + rt + 1, m + 1, r);
      }
}

开的是四倍空间. 2倍 3倍都可能RE, 比如[1, 10]区间

但是对于一棵有n个叶子节点的完全二叉树,节点个数为2 *n - 1个(因为每两个集合都需要一个节点去合并,总共需要n-1个非叶节点).

有两种方法可以开两倍空间

1: 用动态申请内存的方法,当然可以一开始设置2*n的内存池,然后每次申请新节点的时候去内存池里面拿就好了

2: 线段树每个节点的l + r是天然满足中序遍历递增的特点的,而且除了叶子节点外,其他点的l + r 值都不同,l + r为偶数的时候会跟左儿子的最右边的节点的标号相同,  然后我们可以给这些节点强行+1, 可以证明+1之后不会跟右边的节点重复, 因此通过如下函数就可以一一映射到

[0, 2*n-2]

1
2
3
int ID(int l, int r) {
    return l + r | l != r;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注