线段树(Segment Tree),一种基于二叉搜索树的数据结构,通过将子问题进行简单的合并从而高效地解决问题(log2)

 用结构体存储线段树

const int MAXN=100000;//节点数
int sav[MAXN+1];//存储初始值
int Mod,N,M;
struct node {
    int val,plus,times;//plus存储加法lazytag,times存乘法
} a[4*MAXN+1];

 建立一棵树(左右儿子递归)

void build(int k,int l,int r) {
    a[k].times=1;
    a[k].plus=0;
    if(l==r) {
        a[k].val=sav[l]%Mod;
        return;
    }
    int mid=(l+r)>>1;//不要打错>>和l,r
    build(k<<1,l,mid);
    build((k<<1)+1,mid+1,r);
    a[k].val=(a[k<<1].val+a[(k<<1)+1].val)%Mod;//建完树要更新当前节点的值=(左儿子+右儿子)
    return;
}

 ※lazytag下传操作

void pushdown(int k,int l,int r) {
    int mid=(l+r)>>1;
    a[k<<1].val=(a[k<<1].val*a[k].times+a[k].plus*(mid-l+1))%Mod;
    a[(k<<1)+1].val=(a[(k<<1)+1].val*a[k].times+a[k].plus*(r-mid))%Mod;
        //更改左右儿子的值,注意(mid-l+1)与(r-mid)
        a[k<<1].times=a[k].times*a[k<<1].times%Mod;
    a[(k<<1)+1].times=a[k].times*a[(k<<1)+1].times%Mod;
    a[k<<1].plus=(a[k<<1].plus*a[k].times+a[k].plus)%Mod;
    a[(k<<1)+1].plus=(a[(k<<1)+1].plus*a[k].times+a[k].plus)%Mod;
        //更改左右儿子的lazytag,注意先乘除再加减,乘法lazytag直接乘
        //加法lazytag先将父亲的乘法lazytag应用后再加上父亲的加法lazytag
    a[k].plus=0;
    a[k].times=1;
    return;
}

 加法更新区间

void update_add(int k,int nl,int nr,int l,int r,int val) {
    if(nl>r||nr<l)return;
    if(nr<=r&&nl>=l) {
        a[k].plus=(a[k].plus+val)%Mod;//直接加
        a[k].val=(a[k].val+val*(nr-nl+1))%Mod;//不要忘记更新值,有多少个儿子就加多少次
        return;
    }
    pushdown(k,nl,nr);//注意先下传
    int mid=(nl+nr)>>1;
    update_add(k<<1,nl,mid,l,r,val);
    update_add((k<<1)+1,mid+1,nr,l,r,val);//mid+1
    a[k].val=(a[k<<1].val+a[(k<<1)+1].val)%Mod;//不要忘记更新值
    return;
}

 乘法更新区间

void update_mul(int k,int nl,int nr,int l,int r,int val) {
    if(nr<l||nl>r)return;
    if(nr<=r&&nl>=l) {
        a[k].val=a[k].val*val%Mod;//直接更新
        a[k].times=a[k].times*val%Mod;
        a[k].plus=a[k].plus*val%Mod;
        return;
    }
    pushdown(k,nl,nr);//还是先下传
    int mid=(nl+nr)>>1;
    update_mul(k<<1,nl,mid,l,r,val);
    update_mul((k<<1)+1,mid+1,nr,l,r,val);
    a[k].val=(a[k<<1].val+a[(k<<1)+1].val)%Mod;//还是不要忘记更新值
    return;
}

 区间查询

int query(int k,int l,int r,int target_l,int target_r) {
    if(target_l>r||target_r<l)return 0;//越界
    if(target_l<=l&&target_r>=r) {
        return a[k].val%Mod;//包含
    }
    pushdown(k,l,r);//先更新
    int mid=(l+r)>>1;//再分治
    return (query(k<<1,l,mid,target_l,target_r)+query((k<<1)+1,mid+1,r,target_l,target_r))%Mod;
}

 用法

build(1,1,N);//建立一棵树
query(1,1,N,x,y);//查询x->y区间的数值和
update_add(1,1,N,x,y,val)//将x->y区间加上一个val
update_mul(1,1,N,x,y,val)//将x->y区间都乘val

2020.8.28 UPDATE 整合SegmentTree

struct SegTree {
#define ls(x) (x<<1)
#define rs(x) (x<<1)+1
#define ll long long
    struct node {
        ll sum,lazy,max,min;
        int l,r;
    };
    const static int MAXN = 100010;
    node a[4*MAXN+5];
    inline void swap(int &a,int &b) {
        int c=a;
        a=b,b=c;
    }
    inline ll max(ll &a,ll &b) {
        return a>b?a:b;
    }
    inline ll min(ll &a,ll &b) {
        return a>b?b:a;
    }
    inline void pushup(int &k) {
        a[k].sum=a[ls(k)].sum+a[rs(k)].sum;
        a[k].max=max(a[ls(k)].max,a[rs(k)].max);
        a[k].min=min(a[ls(k)].min,a[rs(k)].min);
    }
    inline void pushdown(int &k) {
        if(a[k].lazy==0)return;
        a[ls(k)].sum+=a[k].lazy*(a[ls(k)].r-a[ls(k)].l+1);
        a[rs(k)].sum+=a[k].lazy*(a[rs(k)].r-a[rs(k)].l+1);
        a[ls(k)].lazy+=a[k].lazy,a[rs(k)].lazy+=a[k].lazy;
        a[ls(k)].max+=a[k].lazy,a[rs(k)].max+=a[k].lazy;
        a[ls(k)].min+=a[k].lazy,a[rs(k)].min+=a[k].lazy;
        a[k].lazy=0;
    }
    void build(int k,int l,int r,ll *sav) {
        a[k].l=l,a[k].r=r;
        if(l==r) {
            a[k].sum=a[k].max=a[k].min=sav[l];
            return;
        }
        int mid=l+r>>1;
        build(ls(k),l,mid,sav);
        build(rs(k),mid+1,r,sav);
        pushup(k);
    }
    void query(int k,int l,int r,ll &dist,short op) {
        /*
        op = 0 query sum
             1 query max
             2 query min
        */
        if(a[k].l>=l&&a[k].r<=r) {
            if(op==0)
                dist+=a[k].sum;
            if(op==1)
                dist=max(dist,a[k].max);
            if(op==2)
                dist=min(dist,a[k].min);
            return;
        }
        pushdown(k);
        int mid=(a[k].l+a[k].r)>>1;
        if(l<=mid)query(ls(k),l,r,dist,op);
        if(r>mid)query(rs(k),l,r,dist,op);
    }
    void add(int k,int l,int r,ll &x) {
        if(a[k].l>=l&&a[k].r<=r) {
            a[k].sum+=x*(a[k].r-a[k].l+1);
            a[k].max+=x,a[k].min+=x;
            a[k].lazy+=x;
            return;
        }
        pushdown(k);
        int mid=(a[k].r+a[k].l)>>1;
        if(l<=mid)add(ls(k),l,r,x);
        if(r>mid)add(rs(k),l,r,x);
        pushup(k);
    }
} T;

Categories:

Tags:

No responses yet

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

近期评论
归档
分类