【算法与数据结构】——线段树

悠悠 2022-11-15 14:28 186阅读 0赞

## 线段树原理 ##

将\[1,n\]分解成若干特定的自取件(数量不超过4\*n),然后,将每个区间\[L,R\]都分解为少量特定的子区间,通过对这些少量子区间的修改或者统计,来实现快速对\[L,R\]的修改或者统计.  
如图表示:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDg4NDUz_size_16_color_FFFFFF_t_70]

## 线段树属性 ##

*  每个区间的长度是区间内整数的个数;
 *  叶子节点长度为1,不能再分;
 *  若一个结点对应的区间是\[a,b\],则其子区间对应的节点分别是\[a,(a+b)/2\]和\[(a+b)/2+1,b\];
 *  线段树的高度是; l o g 2 ( b − a + 1 ) log\_2(b-a+1) log2(b−a\+1)\+1;
 *  线段树把区间上的任意一条线段都分成不超过2 l o g 2 N log\_2N log2N条

## 线段树的定义 ##

#### 第一种方法 ####

#define maxn 100007 //元素总个数
    int SegTree[maxn<<2];	//线段树
    //int Lazy[maxn<<2]; //延迟更新标记
    int A[maxn];			//原始数组

#### 第二种方法 ####

用结构体数组表示

#define maxn 100007
    int A[maxn];
    struct SegTreeNode{ 
    	int val;			//节点值
    	//int lazy; //懒惰标记,又称延迟更新标记
    }SegTree[maxn<<2];		//定义线段树

## 线段树的构造 ##

// PushUp函数更新结点信息,这里以求和为例
    void PushUp(int rt)
    { SegTree[rt].val = SegTree[rt<<1].val + SegTree[rt<<1|1].val;}
    void build(int l,int r,int rt) 	//构造根为rt,A区间为[1,r]线段树
    { 	if(l==r){ 			//叶子节点
    	SegTree[rt].val=A[l];
    	return;
    	}
    	int m = (l+r)/2;
    	build(l,m,rt*2);		//递归构造左子树
    	build(m+1,r,rt*2+1);	//递归构造右子树
    	PushUp(rt);		//回溯,向上更新
    }

## 单点更新 ##

假设原始数组A\[L\]+=c

//l,r表示当前结点区间,rt表示当前线段树的根节点编号
    void Update(int L,int C,int l,int r,int rt){ 
    	if(l==r){ 	//叶节点直接修改
    	SegTree[rt].val += C;
    	return ;
    	}
    	int m=(l+r)>>1;
    	if(L <= m)
    	Update(L,C,l,m,rt<<1);
    	else
    	Update(L,C,m+1,r,rt<<1|1);
    	PushUp(rt);	//回溯,向上更新
    }

## 区间查询 ##

//[L,R]表示操作区间,[l,r]表示当前区间,rt表示当前节点编号
    int Query(int L,int R,int l,int r,int rt){ 
    	if(L<=l && r <= R)
    	return SegTree[rt].val;	//在区间内直接返回
    	if(L > r || R < l)
    	return 0;
    	int m = ( l + r ) >> 1;
    	int ANS = 0;
    	if(L <= m) ANS+=Query(L,R,l,m,rt<<1);	//左子区间与[L,R]有重叠,递归
    	if(R > m) ANS += Query(L,R,m+1,r,rt<<1|1);	//右子区间与[L,R]有重叠,递归
    	return ANS;
    	// return Query(L,R,l,m,rt<<1)+Query(L,R,m+1,r,rt<<1|1);//与上面递归部分等价
    }

## 线段树的区间更新 ##

#### 区间更新: ####

是指更新某个区间内的所有叶子节点的值,因为叶子节点会影响其相应的非叶父节点,那么回溯需要更新的非叶子节点也会有很多,如果一次性更新完,操作的时间复杂度可达O(n).  
为此,引入了线段树中的延迟标记概念,(又称为懒惰标记),这也是线段树的精华所在.

#### 延迟标记: ####

每个节点新增一个标记,记录这个节点是否进行了某种修改(这种修改操作会影响其子节点),对于任意区间的修改,我们先按照区间查询的方式将其划分成线段树中的节点,然后修改这些节点的信息,并给这些节点标记上代表这种修改操作的标记.  
在修改和查询的时候,如果我们到了一个节点p,并且决定考虑其子节点,那么我们就要看节点p是否被标记,如果有,就要按照标记修改器子节点的信息,并且给子节点都标上相同的标记,同时消掉节点p的标记.

#### 延迟更新的意义: ####

懒惰理由:1.多次更新,一次下推  
2.无需要,不下推;  
懒惰原则:可以懒惰但是不可以出错(不主动,不拒绝,但负责)

## 加入延时标记后的线段树构造 ##

void build(int l,int r,int rt) 	//构造根为rt,A区间为[1,r]线段树
    { 	
    	SegTree[rt].lazy=0;		//初始化延时标记为0
    	if(l==r){ 			//叶子节点
    	SegTree[rt].val=A[l];
    	return;
    	}
    	int m = (l+r)/2;
    	build(l,m,rt*2);		//递归构造左子树
    	build(m+1,r,rt*2+1);	//递归构造右子树
    	PushUp(rt);		//回溯,向上更新
    }

## 加入延时标记后的区间更新 ##

以A\[L,R\]+=C为例

void Update(int L,int R,int C,int l,int r,int rt){ 
    	if(L<=l&&r<=R){ 
    	SegTree[rt].val+=C*(r-l+1);	//更新数字和,向上保持正确
    	SegTree[rt].lazy+=C;		//累加还是赋值,看需求
    	return;
    }
    	int m=(l+r)>>1;
    	PushDown(rt,m-l+1,r-m);	//下推以后,才准确更新子节点
    	if(L <= m) Update(L,R,C,l,m,rt<<1);
    	if(R > m) Update(L,R,C,m+1,r,rt<<1|1);
    	PushUp(rt);				//更新本节点信息
    }
    //ln,rn分别为左子树和右子树的区间大小
    void PushDown(int rt,int ln,int rn){ 
    	if(SegTree[rt].lazy){ 
    		SegTree[rt<<1].lazy+=SegTree[rt].lazy;
    		SegTree[rt<<1|1].lazy+=SegTree[rt].lazy;
    		SegTree[rt<<1].val +=SegTree[rt].lazy * ln;
    		SegTree[rt<<1].val +=SegTree[rt].lazy * rn;
    		
    		SegTree[rt].lazy = 0;	//清除本节点标记，目的是放置查询的时候重复使用懒标记，如果是赋值也需要注意将懒标记重复使用
    	}
    	//赋值型懒标记
    	/* if(SegTree[rt].lazy!=-1){ SegTree[rt<<1].lazy=SegTree[rt].lazy; SegTree[rt<<1|1].lazy=SegTree[rt].lazy; SegTree[rt<<1].val =SegTree[rt].lazy * ln; SegTree[rt<<1].val =SegTree[rt].lazy * rn; SegTree[rt].lazy = -1; } */
    }

## 区间更新的区间查询 ##

询问A\[L,R\]的和

//[L,R]表示操作区间,[l,r]表示当前区间,rt表示当前区间根节点的编号
    int Query(int L,intR,int l,int r,int rt){ 
    	if(L <= 1&&r<=R)
    	return SegTree[rt].val;	//在区间内直接返回
    	if(L > r||R <l)
    	return 0;
    	int m = (l+r)>>1;
    	PushDown(rt,m-l+1,r-m);	//下推以后,才准确查询子节点
    	return Query(L,R,l,m,rt << 1)+ Query(L,R,m+1,r,rt << 1|1)
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDg4NDUz_size_16_color_FFFFFF_t_70]: /images/20221022/167aa172ce7242d38bf3d3a09c3496c7.png