模板见于页面底端

线段树是一种常用的数据结构,一般可以处理区间最值和区间和,并对区间进行修改。

我们可以想象一个一维数组,二分他的左右,对于分离的两个线段,继续二分… …

是不是很像一个二叉树!

而且是一棵完全二叉树!

这样的话我们可以像二叉树一样,

左儿子编号=2*当前节点编号
右边儿子编号=2*当前节点编号+1

这样的话我们就可以递归建树了【以上两行标重点】。

一.建树与上传

【本文mx数组表示区间最大值,sum表示区间和】

//建树 
void build(int x,int l,int r){
    //最底层时,l-r区间内只有一个元素,最大值&区间和相同
    if(l==r){
        mx[x]=a[l];sum[x]=a[l];
        return;
    }
    int mid = (l+r)/2;//非底层时,二分处理
    build(x*2,l,mid);
    build(x*2+1,mid+1,r);
    pushup(x);//上传标记
}

这里有一个pushup函数,他是一个上传标记的过程,我们递归建树到了最底层,更改(创建)了叶子节点的信息,我们需要把他们上传到父亲节点。

//上传标记 
void pushup(int x){
    mx[x]=max(mx[x*2],mx[x*2+1]);//父最大值=子最大值
    sum[x]=sum[x*2]+sum[x*2+1];//父区间和=子区间和之和
}

之后我们来对线段树进行修改!

线段树的普遍修改/查询要点:

  1. 查询区间在当前区间外,返回;
  2. 查询区间完全覆盖当前区间,计算,返回;
  3. 递归左右子树

二.单点修改【可以略过】

这一部分可以略过,因为单点修改可以用区间为1的区间修改来替代。

不过我们这里的单点修改比区间修改代码量少,简洁【缺点是没有普遍修改要点的明显特征

我们记录一下一下几个量:

当前编号,当前区间左右端点,修改位置,修改大小。

如果当前区间左右端点一样,说明到达目标位置,修改。

否则,计算中点,对左子树或右子树递归。

最后要上传标记

//单点加 
void updata(int x,int l,int r,int pos,int k){//在a[pos]上加k. x是当前节点的编号 
    if(l==r){
        mx[x]+=k;sum[x]+=k;
        return;
    }
    int mid=(l+r)/2;
    if(pos<=mid) updata(x*2,l,mid,pos,k);
    else updata(x*2+1,mid+1,r,pos,k);
    pushup(x);
}

三.区间修改与下传标记

区间修改需要以下几个量:

当前节点标号,当前区间左右端点,修改区间左右端点,修改大小。

那么我们可以套用常规思路
1. 查询区间在当前区间外,返回;
1. 查询区间完全覆盖当前区间,计算,返回;

当然为了高效,我们要用到一个东西————lazy tag(懒标记)

懒标记的功能如其名,他把修改不完全下传到叶子,而是在某一层的父亲节点保存下这次操作。

如果之后涉及到这一层的儿子节点就下传懒标记,

如果不涉及儿子节点,而使用父节点区间整体那么递归到这一层就可以停止。

为了这个目的,我们使用tag数组保存懒标记的操作;

//下传标记
void pushdown(int x,int l,int r){
    if(tag[x]){//如果访问的这个点有懒标记
        int mid=(l+r)/2,ls=x*2,rs=x*2+1;
        tag[ls]+=tag[x];//左右子树加上懒标记
        mx[ls]+=tag[x];//最大值+=懒标记的值
        sum[ls]+=tag[x]*(mid-l+1);//区间和,算出项数再相乘,快速得出。
        tag[rs]+=tag[x];
        mx[rs]+=tag[x];
        sum[rs]+=tag[x]*(r-(mid+1)+1);
        tag[x]=0;//本节点懒标记使用完毕,清空
    }
}

有了这个懒标记我们就可以区间修改了

//区间加 
void updata_(int x, int l, int r, int ll, int rr,int k){//l,r是当前区间;ll,rr是更改区间(本文之后代码同理)
    if(ll>r || rr<l) return;//超出范围,返回
    if(l>=ll && r<=rr){//完全覆盖,修改懒标记
        tag[x]+=k;
        mx[x]+=k;
        sum[x]+=k*(r-l+1);
        return;
    }
    pushdown(x,l,r);//一般情况下,下传标记
    int mid=(l+r)/2;
    updata_(x*2,l,mid,ll,rr,k);//递归~
    updata_(x*2+1,mid+1,r,ll,rr,k);
    pushup(x);//最终更改到叶子节点,为了维护整个线段树,上传标记。
}

如果想要进行单点修改,只需要把ll和rr设定一样即可。

四.查询区间最值

我们讲解最大值,最小值同理。

有一个很显然的道理:

某一层的区间最大值,要么等于左子树最大值,要么等于右子树最大值。

所以这两个最大值里更大的一个就是当前层的区间最大值。

那么我们可以套用常规思路
1. 查询区间在当前区间外,返回;
1. 查询区间完全覆盖当前区间,计算,返回;

if(rr<l || ll>r) return 0;//不相交
if(l>=ll && r<=rr) return mx[x];//当前区间被查询区间所包含

完整代码如下:

int query(int x,int l,int r,int ll,int rr){//l r是当前区间 ll rr是查询区间 
    if(rr<l || ll>r) return 0;//不相交
    if(l>=ll && r<=rr) return mx[x];//当前区间被查询区间所包含
    //其他情况
    int mid=(l+r)/2;
    return max(query(x*2,l,mid,ll,rr),query(x*2+1,mid+1,r,ll,rr)); 
} 

五.查询区间和

略难,但其实有了我们之前区间修改的经验这里并不困难。

常规判断略过。

首先我们要下传标记,把修改下传;

之后递归查询,

然后上传标记

返回查询值。

注意这里要上传标记,直接返回会影响下一次查询!

看代码~

long long query_(int x,int l,int r,int ll,int rr){
    if(rr<l || ll>r) return 0;//不相交
    if(l>=ll && r<=rr) return sum[x];//当前区间被查询区间所包含
    pushdown(x,l,r);
    int mid=(l+r)/2;
    long long ans=query_(x*2,l,mid,ll,rr)+query_(x*2+1,mid+1,r,ll,rr);
    pushup(x);
    return ans;
}



完整代码如下:

int n,m;
long long a[N],sum[N],mx[N],tag[N];
//sum[x]表示x节点代表的区间和, mx[x]代表最大值,tag[x]是x节点的懒标记,代表区间加合 
//上传标记 
void pushup(int x){
    mx[x]=max(mx[x*2],mx[x*2+1]);
    sum[x]=sum[x*2]+sum[x*2+1];
}
//建树 
void build(int x,int l,int r){
    if(l==r){
        mx[x]=a[l];sum[x]=a[l];
        return;
    }
    int mid = (l+r)/2;
    build(x*2,l,mid);
    build(x*2+1,mid+1,r);
    pushup(x);
}
//单点加 
void updata(int x,int l,int r,int pos,int k){//在a[pos]上加k. x是当前节点的编号 
    if(l==r){
        mx[x]+=k;sum[x]+=k;
        return;
    }
    int mid=(l+r)/2;
    if(pos<=mid) updata(x*2,l,mid,pos,k);
    else updata(x*2+1,mid+1,r,pos,k);
    pushup(x);
}
//区间最大值 
int query(int x,int l,int r,int ll,int rr){//l r是当前区间 ll rr是查询区间 
    if(rr<l || ll>r) return 0;//不相交
    if(l>=ll && r<=rr) return mx[x];//当前区间被查询区间所包含
    //其他情况
    int mid=(l+r)/2;
    return max(query(x*2,l,mid,ll,rr),query(x*2+1,mid+1,r,ll,rr)); 
} 
//标记下传(lazytag懒标记)
void pushdown(int x,int l,int r){
    if(tag[x]){
        int mid=(l+r)/2,ls=x*2,rs=x*2+1;
        tag[ls]+=tag[x];
        mx[ls]+=tag[x];
        sum[ls]+=tag[x]*(mid-l+1);
        tag[rs]+=tag[x];
        mx[rs]+=tag[x];
        sum[rs]+=tag[x]*(r-(mid+1)+1);
        tag[x]=0;
    }
}
//区间加 
void updata_(int x, int l, int r, int ll, int rr,int k){
    if(ll>r || rr<l) return;
    if(l>=ll && r<=rr){
        tag[x]+=k;
        mx[x]+=k;
        sum[x]+=k*(r-l+1);
        return;
    }
    pushdown(x,l,r);
    int mid=(l+r)/2;
    updata_(x*2,l,mid,ll,rr,k);
    updata_(x*2+1,mid+1,r,ll,rr,k);
    pushup(x);
}
//区间和 
long long query_(int x,int l,int r,int ll,int rr){
    if(rr<l || ll>r) return 0;//不相交
    if(l>=ll && r<=rr) return sum[x];//当前区间被查询区间所包含
    pushdown(x,l,r);
    int mid=(l+r)/2;
    long long ans=query_(x*2,l,mid,ll,rr)+query_(x*2+1,mid+1,r,ll,rr);
    pushup(x);
    return ans;
}

如果你想AC模板线段树1(洛谷),你可以加上下面这段主函数:

int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    int q,w,e,r;
    build(1,1,n);
    for(int i=1;i<=m;i++){
        scanf("%d",&q);
        if(q==1){
            scanf("%d %d %d",&w,&e,&r);
            updata_(1,1,n,w,e,r);
        }
        if(q==2){
            scanf("%d %d",&w,&e);
            printf("%lld\n",query_(1,1,n,w,e));
        }
    }
    return 0;
}

0 条评论

发表评论

Avatar placeholder

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