线段树 2

动态开点线段树

如果维护序列的长度很大而用到的点比较少我们就不能只使用普通线段树的 p<<1 的方法维护儿子节点了，这样的空间复杂度为 $O(n)$，难以承受。

于是我们使用指针存储儿子节点的位置，在需要用到一个节点的时候动态开点，这样一次操作只会新建 $O(\log_2 n)$ 个新节点，空间复杂度就降至 $O(q\log_2 n)$。

当修改操作将要进入一个节点时，如果当前节点为空，就分配一个新位置给这个节点。因为没有普通线段树的 Build 操作，如果还需要维护区间长度之类的信息必须 手动赋值。

void NewNode(int &p) {                    // 如果有区间长度需要手动赋值如:
    p=++idx;                              // sum(p)={l..r};
}                                         // 新建一个从 l 到 r 的空元素区间

例如 Change 函数中我们在进入儿子节点时，如果儿子未创建就调用 NewNode。需要注意的是，在动态开点线段树里我们使用 l+((r-l)>>1) 而不是 l+r>>1 求 mid，因为后者可能在大值域时溢出。

void Change(int p,int l,int r,int x,Info k){
    if(l==r) return sum(p)=k;
    PushDown(p);
    int mid=l+((r-l)>>1);
    if(x<=mid){
        if(!ls(p)) ls(p)=NewNode();
        Change(ls(p),l,mid,x,k);
    }else{
        if(!rs(p)) rs(p)=NewNode();
        Change(rs(p),mid+1,r,x,k);
    }
    PushUp(p);
}

如果是查询操作进入一个空节点，可以直接返回空区间信息(单位元)，不用新建节点。模板代码如下：

权值线段树

线段树二分

线段树扫描线

线段树分治