动态开点线段树

luckydrawbox · 2021-08-30 21:58:14 · 个人记录

和线段树一样，模板中的函数请根据需要自己补充完成，使用前要建树，其实只是多了建点 \text{make} 操作。

同时你也可以通过 DOP\_S\_T\_T 更改线段树维护的基本类型。

#define DOP_S_T_T int

上面的基础类型是 \text{int}。

#define pl a[p].tl
#define pr a[p].tr
#define DOP_S_T_T int
struct DOP_Segment_Tree{
    int root,tot;
    struct Tree{
        int l,r;
        int tl,tr;
        int tag;
        DOP_S_T_T val;
    }a[N*4];
    void pushup(int p){
        ;
    }
    void pushdown(int p){
        ;
    }
    void make(int p){
        if(!pl){
            int mid=(a[p].l+a[p].r)>>1;
            a[pl=++tot].l=a[p].l;
            a[pl].r=mid;
            a[pr=++tot].l=mid+1;
            a[pr].r=a[p].r;
        }
    }
    void build(int l,int r){
        root=tot=1;
        a[root].l=l;
        a[root].r=r;
    }
    void change(int p,int l,int r,DOP_S_T_T v){
        if(l<=a[p].l&&a[p].r<=r){
            ;
            return;
        }
        make(p);
        pushdown(p);
        int mid=(a[p].l+a[p].r)>>1;
        if(l<=mid)
            change(pl,l,r,v);
        if(r>mid)
            change(pr,l,r,v);
        pushup(p);
    }
    DOP_S_T_T ask(int p,int l,int r){
        if(l<=a[p].l&&a[p].r<=r){
            ;
            return ;
        }
        make(p);
        pushdown(p);
        int mid=(a[p].l+a[p].r)>>1;
        DOP_S_T_T ans=0;
        if(l<=mid)
            ans+=ask(pl,l,r);
        if(r>mid)
            ans+=ask(pr,l,r);
        return ans;
    }
}tree;

空间复杂度 O(m\log n)，m 为常规操作的调用次数，\text{build} 的时间复杂度为 O(1)，其余常规操作复杂度为 O(\log n)。