线段树模板-白红宇的个人博客

线段树模板

发布日期：2021-06-29 05:37:49 浏览次数：2 分类：技术文章

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

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树，最后的子节点数目为N，即整个线段区间的长度。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，因此有时需要离散化让空间压缩。

线段树主要是解决一个区间内的更新和查询，又分为单点更新区间查询，区间更新单点查询，区间更新区间查询。

1、单点更新，区间查询。

这是最简单的线段树，先初始化构造这棵树，然后可以进行两种操作：更新和查询，查询又分为查询区间和sum及区间最值。详细见下面代码：

#include 
    
     #include 
     
      #define N 1000005using namespace std;struct node {	int l,r,sum,m;//sum为和，m为最大值 };	node a[N];void build(int l,int r,int i){	a[i].l=l;	a[i].r=r;	a[i].m=0;	a[i].sum=0;	if(l==r)return;	int mid=(l+r)/2;	build(l,mid,i*2);	build(mid+1,r,i*2+1);}void update(int i,int p,int x)//i为此时结点的位置，p为目标位置 x为插入的数值 {	if(a[i].l==a[i].r)	{		a[i].m=x;		a[i].sum=x;		return;	}	int mid=(a[i].l+a[i].r)/2;	if(p>mid)		update(i*2+1,p,x);	else		update(i*2,p,x);	a[i].m=max(a[i*2].m,a[i*2+1].m);	a[i].sum=a[i*2].sum+a[i*2+1].sum;}int find_max(int l,int r,int i)//l和r为询问区间的范围,i为当前结点 {	if(a[i].l == l && a[i].r == r)		return a[i].m;	int mid = (a[i].l+a[i].r)/2;	if(l>mid)		return find_max(l,r,i*2+1);	else if(r<=mid)		return find_max(l,r,i*2);	else		return max(find_max(l,mid,i*2),find_max(mid+1,r,i*2+1));	}int find_sum(int l,int r,int i){	if(a[i].l==l&&a[i].r==r)		return a[i].sum;	int mid=(a[i].l+a[i].r)/2;	if(l>mid)		return find_sum(l,r,i*2+1);	else if(r<=mid)		return find_sum(l,r,i*2);	else		return find_sum(l,mid,i*2)+find_sum(mid+1,r,i*2+1);}int main(){	int m,n,p,x,y;	scanf("%d%d",&m,&n);	build(1,m,1);	for(int i=1;i<=m;i++)	{		scanf("%d",&x);		update(1,i,x);	}	for(int i=0;i

2、区间更新，单点查询

区间更新需要用到一种lazy思想，修改一个区间的值时，不必每次都修改区间内的每个点，在这个区间的父结点做个标记即可，只有在必要时，才进行修改，这样就减少了修改的次数，节省时间。

具体说的话，主要是体现在两个方面。第一，更新时，如果当前区间就是要更新的区间，那么把这个区间要更新的值记录在这个结点的tag，不再继续往下更新，直接return，这是与常规线段树的一个区别；如果当前区间大于要更新的区间，那么先把之前做的标记传递给子结点并清空当前结点标记，然后再进行更新。第二，查询时，如果要查询当前区间的一个子区间并且当前区间有标记，那么先把标记传递给子结点并清空当前结点标记，再进入子区间内查询。

区间更新，单点查询的代码如下：

（以这个题为例：给n个气球，一共n次操作，每次给（l,r）区间的气球涂上一种颜色，最后输出每种气球的颜色数目）

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int maxn = 100005;struct node{	int l, r, x, tag;	//tag为标记 }; node a[maxn * 4];void init(int l,int r, int i){	a[i].l = l, a[i].r = r;	a[i].x = a[i].tag = 0;	if(l == r) return;	int mid = (l + r) / 2;	init(l, mid, i * 2);	init(mid + 1, r, i * 2 + 1);}void push_down(int i){	if(a[i].tag == 0)return ;	a[i*2].tag += a[i].tag;	a[i*2+1].tag += a[i].tag;	a[i].tag = 0;}void update(int l, int r, int i){	if(a[i].l == l && a[i].r == r){		a[i].tag ++;		return ;	}	push_down(i);	int mid = (a[i].l + a[i].r)/2;	if(l > mid) update(l, r, i*2+1);	else if(r <= mid) update(l, r, i*2);	else{		update(l, mid, i*2);		update(mid+1, r, i*2+1);	}}int search(int i, int p){//i为当前位置，p为目标位置 	if(a[i].l== a[i].r)return a[i].tag;	push_down(i);	int mid = (a[i].l + a[i].r)/2;	if(p > mid)return search(i*2+1, p);	return search(i*2, p);}int main(){	int n, l, r;	while(scanf("%d", &n) && n){		init(1, n, 1);		for(int i = 0; i < n; i ++){			scanf("%d%d",&l, &r);			update(l, r, 1);		}		for(int i = 1; i

3、区间更新，区间查询

这种与第2中相似，不同之处在于update和push_down时维护的值是一个区间的，如果是要查询区间的和的话，那么维护时父结点的sum变化应该是加上tag*len，len为这个区间的长度。具体见下面代码：

以poj3468为例，

给你N个数，Q个操作，操作有两种，‘Q a b ’是询问a~b这段数的和，‘C a b c’是把a~b这段数都加上c，代码如下：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;#define N 100001typedef long long ll;struct node{	int l, r;	ll sum, tag;};node a[N*4];void push_up(int i){	a[i].sum = a[i<<1].sum + a[i<<1|1].sum;}void push_down(int i){	if(a[i].tag == 0)return;	int lchild = i<<1;	int rchild = i<<1|1;	a[lchild].tag += a[i].tag;	a[lchild].sum += a[i].tag * (a[lchild].r-a[lchild].l+1);	a[rchild].tag += a[i].tag;	a[rchild].sum += a[i].tag * (a[rchild].r-a[rchild].l+1);	a[i].tag = 0;}void build(int l, int r, int i){	a[i].l = l;	a[i].r = r;	a[i].tag = 0;	if(l == r){		scanf("%lld", &a[i].sum);		return;	}	int mid = (l + r) >> 1;	build(l, mid, i<<1);	build(mid+1, r, i<<1|1);	push_up(i);}void update(int l, int r, int i, ll c){	if(a[i].l==l && a[i].r==r){		a[i].tag += c;		a[i].sum += (r-l+1)*c;		return;	}	if(a[i].l==a[i].r)return;	push_down(i);	int mid = (a[i].l+a[i].r) >> 1;	if(l > mid) update(l, r, i<<1|1, c);	else if(r <= mid) update(l, r, i<<1, c);	else{		update(l, mid, i<<1, c);		update(mid+1, r, i<<1|1, c);	}	push_up(i);}ll find_sum(int l, int r, int i){	if(a[i].l==l && a[i].r==r){		return a[i].sum;	}	push_down(i);	int mid = (a[i].l+a[i].r)>>1;	if(l > mid) return find_sum(l, r, i<<1|1);	else if(r <= mid) return find_sum(l, r, i<<1);	else return find_sum(l, mid, i<<1) + find_sum(mid+1, r, i<<1|1);}int main(){	int n, q;	while(cin>>n>>q){		build(1, n, 1);		char str[2];		int a, b;		ll c;		while(q--){			scanf("%s", str);			if(str[0] == 'Q'){				scanf("%d%d", &a, &b);				ll ans = find_sum(a, b, 1);				printf("%lld\n", ans);			}			else if(str[0] == 'C'){				scanf("%d%d%lld", &a, &b, &c);				update(a, b, 1, c);			}		}	}	return 0;}

以上总结都是线段树的基础，具体题目需要灵活变化某些变量和维护的数值。

下面是一些线段树的题目（摘自）

1.改点求段

1）点改变（增加，减小，替换），求某段的和

HDU1166 敌兵布阵

2）点改变（增加，减小，替换），求某段最大小值

HDU1754 I Hate It

POJ3264 Balanced Lineup

2.改段求段

1)改段求段（段增减）

poj 3468 A Simple Problem with Integers

2）改段求段（段替换）

HDU1698 Just a Hook

POJ2528 Mayor's posters

ZOJ1610 Count the Colors

HDU3974 Assign the task

HDU4578 Transformation

HDU4614 Vases and Flowers

3）区间合并

POJ3667 Hotel

HDU1540 Tunnel Warfare

HDU4553 约会安排

转载地址：https://blog.csdn.net/zhj_fly/article/details/76367522 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：poj3264 Balanced Lineup——线段树

下一篇：组合数取模

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章