重要算法线段树入门

　　部分图片是从网络获得，侵删！
　　熊猫人线段树什么是线段树
　　入门算法的同学一定对数据结构的线段树不陌生，线段树也是算法比赛常考且非常重要的一种高效解决区间的方法。线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。 下面我会对线段树的基本方法展开详细的介绍。线段树的概念
　　线段树是一种二叉搜索树，什么叫做二叉搜索树，首先满足二叉树，每个结点度小于等于二，即每个结点最多有两颗子树，何为搜索，我们要知道，线段树的每个结点都存储了一个区间，也可以理解成一个线段，而搜索，就是在这些线段上进行搜索操作得到你想要的答案。
　　建立一个线段树的时间复杂度是O(N)（不是O(nlogn)！！）使用线段树可以快速地查找某一个节点在若干条线段中出现的次数，其查找的时间复杂度为O(logN）。而未优化的空间复杂度为O(2N)，因此有时需要离散化让空间压缩。
　　线段树采用分治思想（主要是二分法， 一般可以高效率地解决区间问题。线段树的叶子节点是最简单的节点，叶子节点的父节点是两个叶子节点的区间的并集。对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树，最后的节点数目为N，即整个线段区间的长度。区间[1-5]的线段树如下图所示。
　　1到5区间的线段树线段树使用场景
　　上文已经提到线段树主要是可以高效地解决区间问题，那么具体过程是怎么样的呢？
　　大家可以先看看这个经典选段树的题，后续我会把题解发到推文上 。
　　链接：http://acm.hdu.edu.cn/showproblem.php?pid=1166（无法在内容中引用外文网址 链接我会放在下面）
　　我们打开后我们会发现，这个题目是典型的区间处理题目，但是数据范围极大而且还要处理各种操作，直接用数组存储并遍历操作会直接超时。这时线段树（快且方便）就派上用场了。线段树主要处理极大范围的区间操作。线段树主要代码操作及其讲解线段树的定义
　　父节点val值是所有子节点值的和，这样有利于下面的操作，叶子节点的值就是区间内输入的值。struct Nd //定义线段树节点  { 	int left;//左孩子  	int right;//右孩子  	int val;//该节点值  };
　　2.建树
　　利用递归建立树是常用操作，当r==l时表明到达叶子节点。最后arr[i].val = arr[i<<1].val+arr[i<<1|1].val;是递归回溯时完成子节点对父节点的赋值，因此父节点val值是所有子节点值的和。x<<1与x<<1|1相当于x*=2和x=x*2+1，分别寻找两个子节点。详细如下图所示。
　　父节点对应子节点void build(int l,int r,int i)//利用递归构成线段树  { 	arr[i].left=l;//将左右区间的值赋值给节点  	arr[i].right=r; 	if(r==l) 	{ 		std::cin >> arr[i].val;//最后叶子节点才存储要存储的值 		return ; 	}  	build(l,(l+r)/2,i<<1);//递归到左节点  	build((r+l)/2+1,r,i<<1|1); //递归到右节点  	arr[i].val = arr[i<<1].val+arr[i<<1|1].val;//递归回溯时完成子节点对父节点的赋值  }
　　arr[i].val = arr[i<<1].val+arr[i<<1|1].val;完成时的值是下面所有节点（有亲缘关系）的和，递归是从深到浅，从左到右（左右可变）遍历的过程（DFS就是如此）。
　　3.DFS打印树
　　这个是方便看树每一个节点以及是否健全，找bug用~void dfs_print(int l,int r,int i) { 	/*if(r==l) 	{ 		std::cout << arr[i].val << ＂ ＂;//打印叶子节点  		return ; 	}*/ 	std::cout << arr[i].val << ＂ ＂; 	if(r==l) 	{ 		return ; 	} 	dfs_print(l,(l+r)/2,i<<1); 	dfs_print((r+l)/2+1,r,i<<1|1);  }
　　4.更新节点
　　arr[d].left==arr[d].right时就是叶子，别忘了对父节点回溯时的刷新值。递归找叶节点后更改，void update(int d,int r,int b)// d为当前节点 r为更新的节点 b为改变节点的值 这个递归算法实际就是二分查找  { 	if(arr[d].left==arr[d].right)//递归到叶子节点时 肯定下标是r 注意只能更改叶子节点  	{ 		arr[d].val=b;//更改值  		return; 	}	 	int mid = (arr[d].left+arr[d].right)>>1; 	if(r>mid)update(d<<1|1,r,b);//递归到右son 	else 	update(d<<1,r,b);//递归到左son 	arr[d].val = arr[d<<1].val+arr[d<<1|1].val;//递归回溯时完成子节点对父节点的赋值  }
　　5.区间查询（返回区间内所有节点和）
　　将范围一步一步划分小，充分利用父节点的值增加效率。//区间查询 我们不要忘记，父节点可是存储着它俩儿子值的和  int query(int d,int l,int r)//这个是返回区间的和  { 	int sum = 0;//区间总和 	if(l==arr[d].left&&r==arr[d].right)//1.如果在目的范围内的父亲节点 可以增加效率 		sum += arr[d].val; 	else{ 		int mid = ((arr[d].left+arr[d].right)/2); 		if(l<=mid)		 			(r>mid)?sum+=query(d<<1,l,mid):sum+=query(d<<1,l,r); 		if(r>mid) 			(l<=mid)?sum+=query(d<<1|1,mid+1,r):sum+=query(d<<1|1,l,r); 	} 	return sum; }
　　父节点存储所有子节点的总值，所以我们只需查找范围内的父节点即可。可能您不明白9到12行代码的意义以及如何利用父节点查找：请看下面的图片
　　分割操作
　　虽然图片只有两种情况，别忘了有左右两个子节点，所有必须有四个if判断(代码中部分用三目式代替)。当l==arr[d].left&&r==arr[d].right（分割的目的范围与节点范围相同时返回值）
　　6.单节点查询
　　其实直接调用区间查询即可，两个范围一样就是单节点，这样效率不会影响，还是O(logn)//单点查询 直接调用区间查询即可 效率不受影响  int find(int d,int o)//d 为当前节点 o为查询节点 { 	return query(d,o,o);	 }
　　7.区间修改
　　8-12行代码原理如上图所示。将区间范围一步一步划分为节点操作，这样只需要一个递归就可以解决，具有很高的效率，别忘了父节点的值。void changeSegment(int d,int l,int r,int x)//l和r是修改的范围 x是范围内每一个节点改变的值 { 	if(arr[d].left==l&&arr[d].right==r&&arr[d].left==arr[d].right){//一定要修改叶子节点 不要误修改父节点 		arr[d].val+=x; 		return ; 	}else{ 		int mid = ((arr[d].left+arr[d].right)/2); 		if(l<=mid)		 			(r>mid)?changeSegment(d<<1,l,mid,x):changeSegment(d<<1,l,r,x); 		if(r>mid) 			(l<=mid)?changeSegment(d<<1|1,mid+1,r,x):changeSegment(d<<1|1,l,r,x); 		arr[d].val = arr[d<<1].val+arr[d<<1|1].val;//回溯 改变父节点的值 	} }测试总代码#include    struct Nd //定义线段树节点  { 	int left;//左孩子  	int right;//右孩子  	int val;//该节点值  };  Nd arr[1 << 10]; //随便设有1024个节点  //初始化  void build(int l,int r,int i)//利用递归构成线段树  { 	arr[i].left=l;//将左右区间的值赋值给节点  	arr[i].right=r; 	if(r==l) 	{ 		std::cin >> arr[i].val; 		return ; 	}  	build(l,(l+r)/2,i<<1);//递归到左节点  	build((r+l)/2+1,r,i<<1|1); //递归到右节点  	arr[i].val = arr[i<<1].val+arr[i<<1|1].val;//递归回溯时完成子节点对父节点的赋值  }  //打印节点  void dfs_print(int l,int r,int i) { 	/*if(r==l) 	{ 		std::cout << arr[i].val << ＂ ＂;//打印叶子节点  		return ; 	}*/ 	std::cout << arr[i].val << ＂ ＂; 	if(r==l) 	{ 		return ; 	} 	dfs_print(l,(l+r)/2,i<<1); 	dfs_print((r+l)/2+1,r,i<<1|1);  }  //更新节点  void update(int d,int r,int b)// d为当前节点 r为更新的节点 b为改变节点的值 这个递归算法实际就是二分查找  { 	if(arr[d].left==arr[d].right)//递归到叶子节点时 肯定下标是r 注意只能更改叶子节点  	{ 		arr[d].val=b;//更改值  		return; 	}	 	int mid = (arr[d].left+arr[d].right)>>1; 	if(r>mid)update(d<<1|1,r,b);//递归到右son 	else 	update(d<<1,r,b);//递归到左son 	arr[d].val = arr[d<<1].val+arr[d<<1|1].val;//递归回溯时完成子节点对父节点的赋值  }  //区间查询 我们不要忘记，父节点可是存储着它俩儿子值的和  int query(int d,int l,int r)//这个是返回区间的和  { 	int sum = 0; 	if(l==arr[d].left&&r==arr[d].right)//1.如果在目的范围内  		sum += arr[d].val; 	else{ 		int mid = ((arr[d].left+arr[d].right)/2); 		if(l<=mid)		 			(r>mid)?sum+=query(d<<1,l,mid):sum+=query(d<<1,l,r); 		if(r>mid) 			(l<=mid)?sum+=query(d<<1|1,mid+1,r):sum+=query(d<<1|1,l,r); 	} 	return sum; } //单点查询 直接调用区间查询即可 效率不受影响  int find(int d,int o)//d 为当前节点 o为查询节点 { 	return query(d,o,o);	 }   void changeSegment(int d,int l,int r,int x) { 	if(arr[d].left==l&&arr[d].right==r&&arr[d].left==arr[d].right){ 		arr[d].val+=x; 		return ; 	}else{ 		int mid = ((arr[d].left+arr[d].right)/2); 		if(l<=mid)		 			(r>mid)?changeSegment(d<<1,l,mid,x):changeSegment(d<<1,l,r,x); 		if(r>mid) 			(l<=mid)?changeSegment(d<<1|1,mid+1,r,x):changeSegment(d<<1|1,l,r,x); 		arr[d].val = arr[d<<1].val+arr[d<<1|1].val; 	} 	 } int main() { 	using namespace std; 	build(1,5,1); 	dfs_print(1,5,1); 	int n,a,x; 	cin >> n >> a >> x; 	/*update(1,n,a); 	dfs_print(1,5,1); 	cout << endl; 	cin >> n >> a; 	cout << ＂sum=＂ << query(1,n,a)<> n; 	cout << find(1,n);*/ 	changeSegment(1,n,a,x); 	dfs_print(1,5,1); 	return 0; } 感谢
　　感谢观看，希望大家能够尽情的指点，如果有什么错误的地方可以指出来。
　　创作不易，如果大家感觉有帮助请点一下赞，谢谢。
　　下回会更新它的一道例题题解，链接如下所示。