建树

一句话理解

建树：递归到底把叶子赋值为原数组，再 pushup。

为什么要学

O(n)。

讲解

build(p,l,r)。l==r 为叶。

例子

void build(int p, int l, int r) {
    if (l == r) { sum[p] = a[l]; return; }
    int mid = (l + r) >> 1;
    build(p<<1, l, mid);
    build(p<<1|1, mid+1, r);
    sum[p] = sum[p<<1] + sum[p<<1|1];
}

后序建。

常见错误

• 叶子没赋值。
• mid 划分无限递归 l=r 没判。