线段树

· · 个人记录

线段树灵活多变，所以模板中的函数请根据需要自己补充完成。

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

#define S_T_T int

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

使用前要 \text{build}，\text{change} 和 \text{ask} 函数已经提供模板。

#define pl p<<1
#define pr p<<1|1
#define S_T_T int
struct Segment_Tree{
    struct Tree{
        int l,r;
        int tag;
        S_T_T val;
    }a[N*4];
    void pushup(int p){
        ;
    }
    void pushdown(int p){
        ;
    }
    void build(int p,int l,int r){
        a[p].l=l;
        a[p].r=r;
        if(l==r){
            ;
            return;
        }
        int mid=(l+r)>>1;
        build(pl,l,mid);
        build(pr,mid+1,r);
        pushup(p);
    }
    void change(int p,int l,int r,S_T_T v){
        if(l<=a[p].l&&a[p].r<=r){
            ;
            return;
        }
        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);
    }
    S_T_T ask(int p,int l,int r){
        if(l<=a[p].l&&a[p].r<=r){
            ;
            return ;
        }
        pushdown(p);
        int mid=(a[p].l+a[p].r)>>1;
        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(4N)，\text{build} 的时间复杂度为 O(n\log n)，其余常规操作复杂度为 O(\log n)。