算法总结–线段树

声明(叠甲):鄙人水平有限,本文为作者的学习总结,仅供参考。


1.线段树介绍

线段树说是算法,更应该算是一种二叉树数据结构的使用。
其每个树的节点表示一个区间,其孩子节点表示该区间二分下来的两个节点,其值可以表示这个区间数据的某种运算,如最值、求和等,以下以数组 [1,2,3,4] 为栗子说明,如下所示,根节点表示区间 [1,4] 的和,其它以此类推。

node:当前区间数的和[区间的左边界,区间的右边界]            10[1,4]                         /                        3[1,2]    7[3,4]                  /        /                1[1]  2[2]  3[3] 4[4]       

有如上所示的二叉树以后我们获取区间和的时间复杂度就从 O(n) 到了 O(logn),但数据量十分庞大时这是十分重要的。当然,在节点维护时需要使用一种特殊的方法进行 —— Lazy-tag 技术,这让修改的和时间复杂为降为了O(logn)。


2.二叉树

上面说过,线段树是二叉树的一种,故在深入线段树时,我们先来了解一下二叉树的一些知识点:

如下编号为 K 的节点对应的左孩子为 K+K,右孩子为 K+K+1
在程序为了提高运行效率常常写成 K<<1 与 K<<1|1

node:节点编号        K                  /                   K<<1   K<<1|1      

3.Lazy-tag 技术

对于线段树来说,Lazy-tag 技术是十分的重要的,这是将时间复杂减小来的原因。
其实现的方法具体来说就是使用一些数来对节点进行标记,从而使只有对应区间的根节点会被进行更改,不其内部的值不做更改,具体代码实现见下文。

4.举个栗子——线段树模板题

题目描述

如题,已知一个数列,你需要进行下面两种操作:

  1. 将某区间每一个数加上 k。
  2. 求出某区间每一个数的和。

这种要多次对不同的区间进行操作,线段树是很好的选择,其代码实现可以分为以下几个步骤

4.1.建树

如论是维护还是查询我们都应该先有一个对应的目标不是

// 创建一个开始编号为 index // 区间为 [l,r] 的一个线段树 void build_tree(int index,int l,int r)     {     // 如果为叶节点,即区间中自有一个数     if(r == l)     {         tree[index] = nums[l];         return;     }     // 递归遍历所有的节点     int m = (r+l) >> 1; // 二分区间     build_tree(index<<1,l,m);// 左孩子     build_tree(index<<1|1,m+1,r);// 右孩子     // 赋值,父节点值为其俩孩子的和     tree[index] = treep[index<<1] + treep[index<<1|1]; } 

4.2.维护线段树

在维护数据时,我使用 Lazy-tag 的方法进行处理,具体步骤如下:

【1】 判断区间 [l,r] 是否在 [x,y] 内
【2】 根据该节点是否被标记来确定是否要进行 lazy-tag的下传,通常使用push_down函数来实现
【3】判断是否进行左右节点的递归
【4】更新父节点的数据

// 父节点的 lazy-tag 向其孩子进行传递 void push_down(int index,int l,int r) {     int m = (l+r)>>1;     // 左孩子     tree[index<<1] += tag[index]*(m-l+1);     tag[index<<1] += tag[index];     // 右孩子     tree[index<<1|] += tag[index]*(r-m);     tag[index<<1|] += tag[index];       // 去除父节点的标志     tag[index] = 0; } // 对编号为 index,区间 [l,r] 的中 [x,y] 进行修改 void update(int index,int l,int r,int x,int y) {     // [1] 判断区间 [l,r] 是否在 [x,y] 内     if(x <= l && y >= r)     {         tree[index] += k*(r-l+1);         tag[index] += k;         return;     }     // [2] 根据该节点是否被标记来确定是否要进行 lazy-tag的下传,通常使用push_down函数来实现     if(tag[index] != 0) push_down(index,l,r);     // [3] 判断是否进行左右节点的递归     int m = (l+r)>>1;     if(x <= m) update(index,l,m,x,y);  // 左边     if(y >  m) update(index,m+1,r,x,y);// 右边      // [4] 更新父节点的数据     tree[index] = treep[index<<1] + treep[index<<1|1]; } 

4.3.查询

需要注意的是,查询时也需要进行 Lazy-tag 的下传

// 查询 [l,r] 中的 [x,y] 区间 ll calc(int index,int l,int r,int x,int y) { 	// [1] [l,r]是否被[x,y]覆盖 	if(x <= l && y >= r) 	{ 		return tree[index];   	}  	// [2] lazy-tag 下传 	if(tag[index] != 0) 		push_down(index,l,r);  	// [3] 递归左右孩子节点,并计算结果  	ll ret = 0; 	int m = (l+r)>>1; 	if(x <= m) ret += calc(index<<1,l,m,x,y);     // 左边  	if(y >  m) ret += calc(index<<1|1,m+1,r,x,y); // 右边  	return ret;  } 

4.4.AC代码

#include <bits/stdc++.h> using namespace std;  #define ll long long int #define N_MAX 100000  int n,m,k; ll nums[N_MAX+1],tree[N_MAX*4+1],tag[N_MAX*4+1];  // 建树 void build_tree(int index,int l,int r) { 	// 初始化标记 	tag[index] = 0; 	// 如果是叶节点 	 	if(l == r) 	{ 		tree[index] = nums[l]; 		return;	 	}  	// 递归遍历所有节点 	int m = (l+r) >> 1;  	build_tree(index<<1,l,m);    // 左孩子 	build_tree(index<<1|1,m+1,r);// 右孩子  	// 父节点的值为两孩子  	tree[index] = tree[index<<1] + tree[index<<1|1]; } // lazy-tag 下传 // 需要对左右孩子的 tag 与值都进行修改  void push_down(int index,int l,int r) { 	int m = (l+r)>>1;  	// 左孩子 	tag[index <<1] += tag[index];			 	tree[index<<1] += tag[index]*(m-l+1);  	// 右孩子 	tag[index <<1|1] += tag[index];		 	tree[index<<1|1] += tag[index]*(r-m);  	// 清除自己的标志	 	tag[index] = 0; }  // 更新线段树节点的数据 void update(int index,int l,int r,int x,int y)  { 	// [1] [l,r]是否被[x,y]覆盖 	if(x <= l && y >= r) 	{ 		// 更新数据与 lazy-tag 		tree[index] += k*(r-l+1); 		tag[index] += k; 		return;	 	}  	// [2] lazy-tag 下传 	if(tag[index] != 0) 		push_down(index,l,r); 	// [3] 递归左右孩子节点 	int m = (l+r)>>1; 	if(x <= m) update(index<<1,l,m,x,y);	 // 左边  	if(y >  m) update(index<<1|1,m+1,r,x,y); // 右边  	// [4] 更新数据 	tree[index] = tree[index<<1] + tree[index<<1|1]; } // 查询 ll calc(int index,int l,int r,int x,int y) { 	// [1] [l,r]是否被[x,y]覆盖 	if(x <= l && y >= r) 	{ 		return tree[index];   	}  	// [2] lazy-tag 下传 	if(tag[index] != 0) 		push_down(index,l,r);  	// [3] 递归左右孩子节点,并计算结果  	ll ret = 0; 	int m = (l+r)>>1; 	if(x <= m) ret += calc(index<<1,l,m,x,y);     // 左边  	if(y >  m) ret += calc(index<<1|1,m+1,r,x,y); // 右边  	return ret;  } void print_tree() { 	cout << "tree: "; 	for(int i = 1;i <= 7;i++) 	{ 		cout << tree[i] << " "; 	} 	cout << endl; }  int main() { 	cin >> n >> m; 	// [1] 获取数据并进行建树 	for(int i = 1;i <= n;i++) 	{ 		cin >> nums[i]; 	 	}  	build_tree(1,1,n); 	 	while(m--) 	{ 		int x,y,op; 		cin >> op >> x >> y; 		if(op == 1) // 更新数据  		{ 			cin >> k; 			update(1,1,n,x,y);  		} 		else 	   // 搜索数据  		{ 			cout << calc(1,1,n,x,y) << endl;	 		}  	} } 

5.参考

洛谷线段树题解
木子喵的算法课
线段树的懒标记与应用
本文到此结束,希望对您有所帮助。

发表评论

相关文章