线段树

普通的写线段树的方法是

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: 求中序遍历在某个节点之前一共有几个点,可以一路往根方向走,如果当前是右儿子,就加上左子树以及当前的父亲的总点数,即sz(left) +1,显然size(left) + 1 = 2 * 左子树的叶子个数,所以最终的答案就是2 * 前面总的叶子个数,分奇偶讨论一下结论就是

叶子节点为l+r

非叶节点如果l+r为奇数,答案为l + r

否则为l + r + 1

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

 

发表评论

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