线段树

线段树

        线段树是树状数组的强化版，它每次对区间进行二分，每一个深度都维护了整个区间，在同一深度里面，每个节点维护的区间长度大致相同，而每深入一层又大致比上一层多一倍的节点，故空间复杂度为Onlgn

节点信息

        每个非叶子节点维护一个区间[l,r]，令mid=(l+r)>>1,则该节点的左儿子维护[l,mid]，右儿子维护[mid+1,r]；
        每个叶子节点维护一个点；

线段树的平衡性

        线段树是一颗几乎完全平衡的树。

线段树的区间操作

        因此当我们对于一个长度为n区间[l,r]进行操作的时候，我们就要操作所有与这些区间相关节点，这些节点数目接近2*N。要操作2*N个节点，，，，复杂度过高，，，问题无法解决。
        我们的操作相当于对树进行函数递归。

对节点分类

        这里我们把这个问题简化一下，对于那些节点对应区间属于[l,r]的我们分为一类，对于那些节点对应区间与[l,r]有交集，但不是[l,r]的子区间的节点我们分为第二类，第二类节点一定是某个第一类节点的父亲节点，借此我们可以在函数回溯时候利用区间加法处理，容易解决。

继续分析复杂度

        我们容易发现第一类节点数目接近ON而第二类节点数目接近OlgN，第二类节点一个一个处理可以接受，第一类节点必须安排一下。可以证明第一类节点恰好可以用OlgN颗子树的所有节点唯一表达。
        在这里我们简化问题为对于OlgN个节点以及OlgN颗子树的操作，

子树的操作

        现在我们只需要考虑对某颗子树进行操作

懒惰标记（懒修改）

        当我们进行修改的时候，我们试着只对该子树的根进行修改，并为其加入一个懒惰标记，表示他的所有子孙都有一个与懒惰标记有关的操作还未进行，(例如整段区间加上d，我们就设懒惰标记为d) ，如此区间修改就不用跑到叶子节点，就成了OlgN
        当我们进行查询时，每当我们查询一个节点，我们要查询的恰好为该节点所对应的区间，直接就处理了；如果不是该区间，而是该区间的某个子区间，那么我们考虑把该区间的懒惰标记下放到左右儿子，然后递归左右儿子，回溯答案。over
        为什么线段树快，因为它把区间分成OlgN个处理，并且每次在树上只跑了OlgN个节点，依据区间加法处理询问，依据区间加法回溯处理修改，依据懒惰标记不实时更新叶子节点。所以线段树快。

线段树和树状数组

        为什么我在开头说线段树是树状数组的强化版，因为树状数组虽然能依据区间加法处理询问，也可以依靠区间加法处理更新，但是它的非叶子节点过少，导致复杂的数据维护时程序较为复杂，不太好处理。

#define ls (u<<1)
#define rs (u<<1|1)
#define ml ((l+r)>>1)
#define mr (ml+1)
struct segment_tree{
    static const ll maxn=2.1e5;
    ll n;
    ll a[maxn],tree[maxn<<2],lazy[maxn<<2];
    //////////////
    //树链剖分接口
    ll rnk[maxn];
    //////////////
    void pushdown(ll u,ll l,ll r){
        //lazy[ls]+=lazy[u];
        //lazy[rs]+=lazy[u];
        //tree[ls]+=lazy[u]*(ml-l+1);
        //tree[rs]+=lazy[u]*(r-mr+1);
        lazy[u]=0;
    }
    void pushup(ll u){
        //tree[u]=tree[ls]+tree[rs];
    }
    void build(ll nn){
        n=nn;
        build(1,n,1);
    }


    void build(ll l,ll r,ll u){
        lazy[u]=0;
        if(l==r){
            //tree[u]=a[rnk[l]];
            return ;
        }

        build(l,ml,ls);
        build(mr,r,rs);
        pushup(u);
    }
    void update(ll ql,ll qr,ll d){
        update(ql,qr,d,1,1,n);
    }
    void update(ll ql,ll qr,ll d,ll u,ll l,ll r){
        if(ql<=l&&r<=qr){
            //tree[u]+=(r-l+1)*d;
            //lazy[u]+=d;
            return ;
        }
        if(lazy[u])pushdown(u,l,r);
        if(ql<=ml)update(ql,qr,d,ls,l,ml);
        if(qr>=mr)update(ql,qr,d,rs,mr,r);
        pushup(u);
    }
    ll query(ll ql,ll qr){
        return query(ql,qr,1,1,n);
    }
    ll query(ll ql,ll qr,ll u,ll l,ll r){
        if(ql<=l&&r<=qr)return tree[u];
        ll ret=0;
        if(lazy[u])pushdown(u,l,r);
        if(ql<=ml)ret+=query(ql,qr,ls,l,ml);
        if(qr>=mr)ret+=query(ql,qr,rs,mr,r);
        return ret;
    }
};

#define ml ((l+r)>>1)
#define mr (ml+1)
const int maxn=5e4+5;
int rev[maxn*2*35],cov[maxn*2*35],sum[maxn*2*35],ls[maxn*2*35],rs[maxn*2*35],a[maxn],tot;

void push_son(int&son,int l,int r,int covrt,int revrt){// 这个函数要注意重写
    if(son==0) {
        son=++tot;
        cov[son]=-1;
        rev[son]=0;
        sum[son]=0;
        ls[son]=0;
        rs[son]=0;
    }
    if(covrt!=-1){
        sum[son]=(r-l+1)*covrt;
        cov[son]=covrt;
        rev[son]=0;
    }
    if(revrt!=0){
        sum[son]=(r-l+1)-sum[son];
        rev[son]^=1;
    }
}

void push_down(int rt,int l,int r){
    push_son(ls[rt],l,ml,cov[rt],rev[rt]);// 这行要注意重写
    push_son(rs[rt],mr,r,cov[rt],rev[rt]);// 这行要注意重写
    cov[rt]=-1; rev[rt]=0;// 这行要注意重写
}

void push_up(int rt,int l,int r){
    sum[rt]=sum[ls[rt]]+sum[rs[rt]];// 这行要注意重写
}

void build(int&rt,int l,int r){
    rt=tot=0;
    push_son(rt,l,r,-1,0);// 这行要注意重写
}

void update(int rt,int l,int r,int ql,int qr,int d,int type){//
    if(ql<=l&&r<=qr){// 这行要注意重写
        if(type==1) push_son(rt,l,r,-1,1);//rev
        if(type==2) push_son(rt,l,r, d,0);//cover
        return;
    }
    push_down(rt,l,r);
    if(ml>=ql) update(ls[rt],l,ml,ql,qr,d,type);
    if(mr<=qr) update(rs[rt],mr,r,ql,qr,d,type);
    push_up(rt,l,r);
}

int query(int rt,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr) return sum[rt];// 这行要注意重写
    push_down(rt,l,r);
    int ret=0;// 这行要注意重写
    if(ml>=ql) ret+=query(ls[rt],l,ml,ql,qr);// 这行要注意重写
    if(mr<=qr) ret+=query(rs[rt],mr,r,ql,qr);// 这行要注意重写
    return ret;
}