线段树入门

参考 https://www.cnblogs.com/AC-King/p/7789013.html

一: 定义

线段树是一棵二叉树，树中的每一个结点表示了一个区间[a,b]。a,b通常是整数。每一个叶子节点表示了一个单位区间。对于每一个非叶子结点所表示的结点[a,b]，其左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2 + 1,b]。

线段树适用于和区间统计有关的问题。比如某些数据可以按区间进行划分，按区间动态进行修改，而且还需要按区间多次进行查询，那么使用线段树可以达到较快查询速度 ,修改和统计的复杂度都是O(log2(n)).。

二：原理

（注：由于线段树的每个节点代表一个区间，以下叙述中不区分节点和区间，只是根据语境需要，选择合适的词）

线段树本质上是维护下标为1,2,..,n的n个按顺序排列的数的信息，所以，其实是“点树”，是维护n的点的信息，至于每个点的数据的含义可以有很多，

在对线段操作的线段树中，每个点代表一条线段，在用线段树维护数列信息的时候，每个点代表一个数，但本质上都是每个点代表一个数。以下，在讨论线段树的时候，区间[L,R]指的是下标从L到R的这(R-L+1)个数，而不是指一条连续的线段。只是有时候这些数代表实际上一条线段的统计结果而已。

线段树是将每个区间[L,R]分解成[L,M]和[M+1,R] (其中M=(L+R)/2 这里的除法是整数除法，即对结果下取整)直到 L==R 为止。

开始时是区间[1,n] ,通过递归来逐步分解，假设根的高度为1的话，树的最大高度为线段树入门（n>1）。

线段树对于每个n的分解是唯一的，所以n相同的线段树结构相同，这也是实现可持久化线段树的基础。

下图展示了区间[1,13]的分解过程：

线段树入门

上图中，每个区间都是一个节点，每个节点存自己对应的区间的统计信息。

根节点存储的永远是总区间

孩子节点每次都把其父亲节点分成两部分，父亲节点表示的区间为[L,R]，其左儿子表示的区间为[L,(L+R)/2]，右儿子表示的区间为[(L+R)/2 + 1,R]。

由此看出，用线段树统计的东西，必须符合区间加法，否则，不可能通过分成的子区间来得到[L,R]的统计结果。

符合区间加法的例子：

数字之和——总数字之和 = 左区间数字之和 + 右区间数字之和

最大公因数(GCD)——总GCD = gcd( 左区间GCD , 右区间GCD );

最大值or最小值——总最大值=max(左区间最大值，右区间最大值)

不符合区间加法的例子：

众数——只知道左右区间的众数，没法求总区间的众数

01序列的最长连续零——只知道左右区间的最长连续零，没法知道总的最长连续零.

三 : 应用举例

维护区间和

给你一个数的序列A1 A2……An。并且可能多次进行下列两个操作：

1、对序列里面的某个数进行加减(或将一个数替换成里一个数)

2、询问这个序列里面任意一个子序列 Ai Ai+1 ……Aj 区间[i,j]的和是多少。

解析：

[1,n]就是根节点对应的区间
可以在每一个节点记录该节点对应的区间的和Sum （具体如何分区间见图2）。
对于操作1：只修改覆盖A[i]节点的Sum值进行加减操作
对于操作2：同样只需要找到区间所覆盖的区域，然后把所找区域的Sum累加起来。

先来看操作2 查询

假设我们要查找区间[3,7]的值我们怎么做呢？如图：

我们先将所要查询的区间与当前区间进行比较，显然[3,7]是在[1,8]的里面的，所以我们就去根节点的两个孩子节点里找自己所需要的求值

线段树入门

然后我们将分开后的区间继续比较。
显然,[3,4]在[1,4]内，所以直接继续去根节点的两个孩子节点里找自己所需要的求值

显然,[5,7]在[5,8]内，所以直接继续去根节点的两个孩子节点里找自己所需要的求值

线段树入门

最后输出9即为[3,7]查询的正解

线段树入门

我们发现：对于[3,4]的这个区间，我们已经预处理过它的值了，所以可以不用继续访问，直接返回。

对于[5,6]的区间，同样是因为全部相等，所以直接返回。

对于[7,8]的区间，因为[7,7]并不能完全覆盖[7,8]，换个意思讲就是[7,8]并不是[7,7]的子区间。这个时候我们只能继续递归到正好满足当前查询区间为目标区间的子区间就可以返回了

实际上这样的工作效率就会非常的高。

查询的思想是选出一些区间，使他们相连后恰好涵盖整个查询区间。

再来看操作1 修改

比如说A[6] += 7;

线段树入门

改变6 这个节点需要一次更新他的父亲节点，直到根节点

线段树入门

单点更新:最最基础的线段树,只更新叶子节点,然后把信息用 PushUP(int r)这个函数更新上来

单点更新,区间查询题目

HH神代码风格:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <set>
#include <cstring>
#include <stack>
#include <set>
#include <vector>
#include <map>
#include <queue>
#define Swap(a,b)  a ^= b ^= a ^= b
#define pi acos(-1)
#define cl(a,b) memset(a,b,sizeof(a))
#define lson rt<<1
#define rson rt<<1|1
using namespace std ;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int MAX = 55555;
int sum[MAX<<2] ;
void PushUP(int rt){ // 向上更新
	sum[rt] = sum[lson] + sum[rson] ;
	return ;
}
void build(int l ,int r , int rt){
	// 建立线段树
	if( l == r )// 到达叶子节点
	{
		scanf("%d",&sum[rt]);
		return ;
	}
	int m = (l+r)>>1 ;
	build(l,m,lson) ;
	build(m+1,r,rson) ;
	PushUP(rt) ;
	return ;
}
void update(int p ,int add ,int l ,int r , int rt){// 单点更新
	if(l == r ){
		sum[rt] +=add;
		return ;
	}
	int m = (l+r)>>1 ;
	if(p<=m) update(p,add,l,m,lson) ;
	else update(p,add,m+1,r,rson) ;
	PushUP(rt) ;
}
int query(int L ,int R , int l ,int r , int rt ){
	// 区间查询
	if(L <=l && r<=R){
		return sum[rt] ;
	}
	int m = (l+r)>> 1 ;
	int ans = 0 ;
	if(L<=m){
		ans+=query(L,R,l,m,lson) ;
	}
	if(R>m){
		ans+=query(L,R,m+1,r,rson) ;
	}
	return ans ;
}
int main()
{
	int T ;
	int t ;
	cin >>T;
	t = T ;
	while(T--){
		int n ;
		char op[10] ;
		cl(sum,0);
		scanf("%d",&n);
		build(1,n,1) ;
		printf("Case %d:\n",t-T);
		while(~scanf("%s",op)){
			int i , j ;
			if(op[0]=='E'){ // 结束
				break ;
			}
			scanf("%d%d",&i,&j);
			if(op[0]=='Q'){ // 区间查询
				
				int ans = query(i,j,1,n,1) ;
				printf("%d\n",ans);
			}
			else if(op[0]=='A'){ // 单点更新
				update(i,j,1,n,1);
			}
			else{
				update(i,-j,1,n,1);
			}

		}
		
	}
	

	return 0 ;
}

线段树功能:update:单点替换 query:区间最值

单点更,区间最值

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <set>
#include <cstring>
#include <stack>
#include <set>
#include <vector>
#include <map>
#include <queue>
#define Swap(a,b)  a ^= b ^= a ^= b
#define pi acos(-1)
#define cl(a,b) memset(a,b,sizeof(a))
#define lson rt<<1
#define rson rt<<1|1
using namespace std ;
typedef long long LL;
//const int N = 1e7+10 ;
const int inf = 0x3f3f3f3f;

const int maxn = 222222;
int MAX[maxn<<2] ;
void PushUP(int rt){ // 向上更新
	MAX[rt] = max(MAX[lson] , MAX[rson]) ;
	return ;
}
void build(int l ,int r , int rt){
	// 建立线段树
	if( l == r )// 到达叶子节点
	{
		scanf("%d",&MAX[rt]);
		return ;
	}
	int m = (l+r)>>1 ;
	build(l,m,lson) ;
	build(m+1,r,rson) ;
	PushUP(rt) ;
	return ;
}
void update(int p ,int sc ,int l ,int r , int rt){
	if(l == r ){
		MAX[rt] = sc;
		return ;
	}
	int m = (l+r)>>1 ;
	if(p<=m) update(p,sc,l,m,lson) ;
	else update(p,sc,m+1,r,rson) ;
	PushUP(rt) ;
}
int query(int L ,int R , int l ,int r , int rt ){
	// 区间查询
	if(L <=l && r<=R){
		return MAX[rt] ;
	}
	int m = (l+r)>> 1 ;
	int ans = 0 ;
	if(L<=m){
		ans = max(ans,query(L,R,l,m,lson) ) ;
	}
	if(R>m){
		ans = max(ans,query(L,R,m+1,r,rson) ) ;
	}
	return ans ;
}
int main()
{
	int n , m ;
	while(~scanf("%d%d",&n,&m)){
		cl(MAX,0);
		build(1,n,1);
		char op[5] ;
		while(m--){
			int a ,b ;
			scanf("%s%d%d",op,&a,&b);
			if(op[0]=='Q'){
				printf("%d\n",query(a,b,1,n,1) );

			}
			else{
				update(a,b,1,n,1);
			}
		}
	}
	

	return 0 ;
}

未完待续..

一: 定义

二：原理

三 : 应用举例

相关推荐