本文共 3114 字，大约阅读时间需要 10 分钟。

线段树原理

将[1,n]分解成若干特定的自取件(数量不超过4*n),然后,将每个区间[L,R]都分解为少量特定的子区间,通过对这些少量子区间的修改或者统计,来实现快速对[L,R]的修改或者统计.

如图表示:

线段树属性

• 每个区间的长度是区间内整数的个数;
• 叶子节点长度为1,不能再分;
• 若一个结点对应的区间是[a,b],则其子区间对应的节点分别是[a,(a+b)/2]和[(a+b)/2+1,b];
• 线段树的高度是;$lo{g}_2(b-a+1)$+1;
• 线段树把区间上的任意一条线段都分成不超过2$lo{g}_{2}N$条

线段树的定义

第一种方法

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

第二种方法

用结构体数组表示

#define maxn 100007int 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<=1 && r <= R)	return SegTree[rt].val;	//在区间内直接返回	if(L > r || R < 1)	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;	//清除本节点标记	}}

区间更新的区间查询

询问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 
   
    >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)}
   

转载地址：http://oybmz.baihongyu.com/