线段树基础

Source
版权声明:转载请注明出处(作者转载的文章除外) https://blog.csdn.net/guoyangfan_/article/details/81130689

维护区间线段树浅谈:

一:引入

在日常OI中,我们时常会遇到一些关于毒瘤区间维护等操作,那么这时候线段树(说到底是一棵二叉查找树)是一个很好的选择。

 

二:了解大概

假设我们有一段区间。

一般来说,我们需要将这一段区间分为两个子区间(一般来说我们都是将一个区间平分为两个子区间。(区间长度是单数?那么就尽量将两个区间的长度差最小)),再由这两个子区间分别分成两个子区间...(如此循环)...直到最后剩余的子区间达到我们预期的状态(一般来说只剩下一个节点)

这时,我们操作时,需要在需要操作的子区间内操作(因为基于二分构树,有log的优化),所以没有必要使用暴力的枚举法或者比这个劣一点的算法去查找(对,查找)我们需要操作的子区间了。

这时你可能就会问了:这样子讲我怎么懂呢QAQ?

别急,让我使用我的灵魂画笔给你来一张图。

如图,我们有一到五的这一个区间(之后我们称为原区间(原是最初的意思))。

我们将第一个区间一分为二,得到(1到2的区间)和(3到5的区间)。其中,这两个所拥有的信息量分别是原区间(1到5的这个区间)的(1到2的区间)的信息 和 (3到5的区间)的信息。

线段树之~  建树操作:

inline void build(int now,int l,int r)
{
	if(l==r){sum[now]=arr[l];minn[now]=arr[l];return;}//如果当前区间的左端点已经是右端点了,那么这个小节点的值便是arr[l],之后我们回溯求出它的父亲;
	int mid=(l+r)/2;//每一个父节点有两个子节点;

	build(now*2,l,mid);
	build(now*2+1,mid+1,r);

	sum[now]=sum[now<<1]+sum[(now<<1)+1];//每一个父节点都由它的两个字节点更新而来;
        minn[now]=min(minn[now<<1],minn[(now<<1)+1]);;
}

 线段树之 ~ 区间询问操作(1)

   线段树区间求最值:

         因为线段树的区间是由它的两个子区间决定的(除了最底层的),所以我们可以用递归快速的将每个子结点求出:

    //PS:上面的代码中minn求的是最小值,所以这里代码只放求(x到y)区间最小值的;

int findmin(int now,int l,int r,int x,int y)//now指当前结点编号,l与r指目前所在的区间,x与y值要查询的区间;
{
	if(l>y || x>r)return 2147483647;//如果当前所在区间的右端点已经大于了要查询的区间,那么返回一个极大值,因为函数返回的是较小值,所以返回极大值表示l到r这段区间不可取;
	if(x<=l && r<=y)return minn[now];//如果目前所在区间在要查询的区间里面了,那么返回已经找到的答案;

	int mid=(l+r)/2;
	return min(findmin(now*2,l,mid,x,y),findmin(now*2+1,mid+1,r,x,y));//求出的最值是在当前节点的子节点的最值。
}

 

线段树之~区间询问操作(2)

    线段树区间求和:每一个区间都由属于它的区间现加而来;

inline int findsum(int now,int l,int r,int x,int y)
{
	if(l>y || x>r)return 0;//如果目前所在的区间不在查询区间内,那么返回0,相当于这里不计算;

	if(x<=l && r<=y)return sum[now];//如果目前所在区间在要查询的区间里面了,那么返回已经找到的答案;
        long long ans=0;
	int mid=(l+r)/2;

	ans+=findsum(now*2,l,mid,x,y);//累加属于当前区间左边区间的值;
	ans+=findsum(now*2+1,mid+1,r,x,y);//累加属于当前区间右边的值;
        return ans;
};

   

线段树之~单点修改操作

           当我们改变最底层的结点的值时,包含它的那段区间的值也会改变,于是更新包含它的那段区间。

            现在,这里的代码放的是求一个区间最小值的:

void change(int now,int l,int r,int x,int s)//now表示当前区间的下标,x表示要修改的点的位置,s表示修改后点的值;
{
      if(r<x || l>x)return;//如果当前查询的区间不包含要修改的点,返回;
      if(l==r && l==x)//如果找到要修改的点;
      {
          minn[now]=s;//将当前下标的点修改;
          return;//返回;
      }
      int mid=(l+r)/2;
      change(now*2,l,mid,x,s);//左边区间;
      change(now*2+1,mid+1,r,x,s);//右边区间;
      minn[now]=min(minn[now*2],minn[now*2+1]);//更新值,当前结点的值是属于它的左右两个结点的最小值;
}

 

线段树之~区间修改,区间询问(好了,到了线段树的主场时间了)

        有时我们需要解决的不只是单点修改,区间询问,而是区间修改,区间询问。此时,单纯的利用上面的操作已经无法解决问题了,因为我们没有办法高效的完成区间修改,如果将区间拆成一个个的点进行修改或是在递归时访问所有被更改的点,那么最坏情况下修改操作的总复杂度就变为O(m*n*logn),比朴素算法还要劣。                                                           

          有两种办法,一是懒标记(标记下传),二是标记永久化                 

          懒标记(lazy)代码【区间求和、区间查询主要部分】:

//Add函数表示我们要制造一个懒标记”;
//add数组相当与记录“懒标记”;
//pushdown 表示将标有懒标记的变量还原;
//modify表示更新我们要求的数组,还原标有懒标记的变量;
//findans表示求出我们要计算的那段区间(x——y);
void Add(int now,int l,int r,int s)
    add[now]+=s;//在这个结点上标记一下,等着pushdown把加的值传下去。
    sum[now]+=(r-l+1)*s;//这个结点要加这么多的值;
}
void pushdown(int now,int l,int r,int mid)//now表示当前数组的下标,mid表示modify传来的那个参数(目前区间的两个子区间的分界线);
{
    if(add[now]==0)return;//若当前的懒标记已经没了,就可以撤了;
    Add(now*2,l,mid,add[now]);//将当前区间的左子区间还原,也就是加上那个懒标记的值;
    Add(now*2+1,mid+1,r,add[now]);//右区间同理;
    add[now]=0;//这个标记使命已经完了;
}
void modify(int now,int l,int r,int x,int y,int s)
{
    if(l>=x && r<=y)return Add(now,l,r,s);//如果在这范围里了,那么懒标记一下,表示这个范围里的值都加上s;
    int mid=(l+r)/2;
    pushdown(now,l,r,mid);//还原懒标记,也就是下传标记,每一个结点都要做一次;
    if(x<=mid) modify(now*2,l,mid,x,y,s);//换了一种写法,意义其实一样;
    if(y>mid) modify(now*2+1,mid+1,r,x,y,s);
    sum[now]=sum[now*2]+sum[now*2+1];
}
int findans(int now,int l,int r,int x,int y)
{
    if(l>=x && r<=y)return sum[now];
    int mid=(l+r)/2,ans=0;
    if(x<=mid)ans+=findans(now*2,l,mid,x,y);
    if(mid<y)ans+=findans(now*2+1,mid+1,r,x,y);
    return ans;
}

     懒标记代码【区间乘法&求和,区间查询主要部分】:

//mul数组表示要乘上的数;(乘法懒标记);
//add数组表示要加上的数;(加法懒标记);
#define ll long long 
const int maxn=100010;
int mod;
ll sum[maxn<<2],add[maxn<<2],mul[maxn<<2],a[maxn];
inline void pushdown(int now,int len)//标记下传;len表示传进来的区间长度;
{
	if(add[now]!=0 || mul[now]!=1)
	{
	  add[now<<1]=(add[now<<1]*mul[now]+add[now])%mod;
	  add[now<<1|1]=(add[now<<1|1]*mul[now]+add[now])%mod;//涉及到了四则运算的优先级,乘法优先级比加法高,所以add要先乘上mul[now];
	  mul[now<<1]=(mul[now<<1]*mul[now])%mod;
	  mul[now<<1|1]=(mul[now<<1|1]*mul[now])%mod;//乘法标记下传
	  sum[now<<1]=(add[now]*(len-(len>>1))%mod+sum[now<<1]*mul[now]%mod)%mod;
	  sum[now<<1|1]=(add[now]*(len>>1)%mod+sum[now<<1|1]*mul[now]%mod)%mod;//这里涉及到了四则运算的优先级以及乘法分配律(结合律?);
	  add[now]=0;
	  mul[now]=1;
	}
}
inline void build(int now,int l,int r)//建树;
{
	mul[now]=1;
	add[now]=0;
	if(l==r){
		sum[now]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(now<<1,l,mid);
	build(now<<1|1,mid+1,r);
	sum[now]=sum[now<<1]+sum[now<<1|1];
}
inline void update1(int now,int l,int r,int x,int y,int s)//乘法
{
	if(l>=x && r<=y){
		add[now]=add[now]*s%mod;
		mul[now]=mul[now]*s%mod;
		sum[now]=sum[now]*(ll)s%mod;
		return;//记录懒标记,不重复说了;
	}
	pushdown(now,r-l+1);//懒标记还原;
	int mid=(l+r)>>1;
	if(mid>=x)update1(now<<1,l,mid,x,y,s);
	if(mid<y)update1(now<<1|1,mid+1,r,x,y,s);
	sum[now]=sum[now<<1]+sum[now<<1|1];
}
inline void update2(int now,int l,int r,int x,int y,int s)//加法
{
	if(l>=x && r<=y){
		add[now]=(add[now]+s)%mod;
		sum[now]=(sum[now]+(r-l+1)*s)%mod;//不重复说了;
		return;
	}
	pushdown(now,r-l+1);
	int mid=(l+r)>>1;
	if(x<=mid)update2(now<<1,l,mid,x,y,s);
	if(mid<y)update2(now<<1|1,mid+1,r,x,y,s);
	sum[now]=sum[now<<1]+sum[now<<1|1];
}
inline long long query(int now,int l,int r,int x,int y)//求和,不重复说了;
{
	if(l>=x && r<=y)return sum[now]%mod;
	pushdown(now,r-l+1);
	long long ans=0;
	int mid=(l+r)>>1;
	if(mid>=x)ans+=query(now<<1,l,mid,x,y);
	if(mid<y)ans+=query(now<<1|1,mid+1,r,x,y);
	return ans%mod;
}

 

      另一种是标记永久化,它不下传add标记,改为询问过程中计算每个遇到的结点对当前询问的影响。为了保证询问的复杂度,子结点的影响需要在修改时计算好。所以,实际上sum的值表示这个区间内所有数共同加上的值,sum表示这个区间除了add之外其他值的和。需要注意的是区间add值有可能有一部分在祖先结点上,在递归时累加即可。这一点和单点询问修改类似。

       这种标记永久化的写法在树套树以及可持久化数据结构较为方便。

        标记永久化代码【区间求和、区间查询】(个人觉得看懂lazy看这个容易理解一点):

void modify(int now,int l,int r,int x,int y,int s)
{
    if(l>=x && r<=y)
    {
        add[now]+=s;
        return;
    }
    sum[now]+=(min(r,y)-max(l,x)+1)*s;//计算子节点对当前结点的影响。
    int mid=(l+r)/2;
    if(x<=mid) modify(now*2,l,mid,x,y,s);
    if(mid<y) modify(now*2+1,mid+1,r,x,y,s);
}
int query(int now,int l,int r,int x,int y)
{
    if(l>=x && r<=y)return sum[now]+(r-l+1)*add[now];
    int mid=(l+r)/2;
    int ans=(min(r,y)-max(l,x)+1)*add(now);//先计算标记影响;
    if(x<=mid) ans+=query(now*2,l,mid,x,y);//计算左区间的值;
    if(mid<y) ans+=query(now*2+1,mid+1,r,x,y);//右区间;
    return ans;
}