个人中心
gpt4 book ai didi

线段树详解（含代码实现经过测试）

转载 作者：知者 更新时间：2024-03-13 07:43:31 26 4
gpt4 key购买 nike

1.线段树介绍

2.线段树原理及其实现

2.1区间修改

2.2区间查询

2.3区间更新

1.线段树介绍

什么是线段树？线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。 [1]

对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树，最后的子节点数目为N，即整个线段区间的长度。

使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN）。而未优化的空间复杂度为2N，因此有时需要离散化让空间压缩。-----来自百度。

2.线段树原理及其实现

线段树主要是把一段大区间 平均地划分 成两段小区间进行维护，再用小区间的值来更新大区间。这样既能保证正确性，又能使时间保持在 log ⁡ 级别（因为这棵线段树是平衡的）。也就是说一个[L,R]区间会被划分为两个区间分别是[L,(L+R)/2]和[(L+R)/2+1,R]这两个小区间。然后再递归下去分直达L=R。
下图就是一棵 [ 1 , 10 ] 的线段树的分解过程（相同颜色的节点在同一层）如图所示：

我们可以发现，这棵线段树的最大深度不超过[ log2   ( n − 1 ) ]+2.

1.实现的基本框架 

我们如何实现这种结构呢？难道真的是用二叉树吗？当然不是我们可以用我们之前学过的堆来实现这种结构。本文中使用满二叉树来实现线段树，可能有老铁会问了如果给定数组的长度不是2的某次方时又该怎么办了？在这里如果他不是满二叉树我们给他补成满二叉树。 

2.空间的计算

实现线代树我采用了大根堆来实现，这是因为大根堆是一个完全二叉树因此我们可以使用数组来表示，只不过当数组的长度不是2^i时我们需要补齐。如图所示

现在我们来估计一下大概需要多少空间。假设区间有n个元素，对于满二叉树来说：

1.第一层到第k层一共有2^k-1个节点（约有2^k）个节点

2.最后一层共有2^k-1个节点

我们可以得出：满二叉树中最后一层节点的个数大约是前面节点的个数之和

1.如果n=2^i则需要2n个节点

2.如果n=2^i+1时此时情况最坏需要4*n个节点（估计值）

3.表示方式：

在这里我们我们数组的下标是从1开始，这是为了让左右孩子的下标能够使用位运算来进而提高效率。如果一个父亲节点对应的索引为i那么则有下面公式：

1.左孩子=2*i;

2.右孩子=2*i+1

用位运算来表示为：

1.左孩子=i<<1;

2.右孩子=i<<1|1;

4.线段树的构建对应代码：

#pragma once 
#include<iostream>
#include<vector>
using std::vector;
using std::cout;
using std::endl;
class SegmentTree {
public:
	SegmentTree(const vector<int>& origin) {
		MAXN = origin.size() + 1;
		arr.resize(MAXN);
		for (int i = 1; i < MAXN; i++) {//arr[0]不用从arr[1]开始
			arr[i] = origin[i - 1];
		}
		sum.resize(MAXN << 2);//相当与MAXN*4；用来支持脑补概念中，某一个范围的累加和信息
		lazy.resize(MAXN << 2);//用来支持脑补概念中，某一个没有在往下的累加和标记
		change.resize(MAXN << 2);
		update.resize(MAXN << 2);

	}
	void build(int l, int r, int rt) {
		if (l == r) {//只有一个数
			sum[rt] = arr[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(l, mid, rt << 1);
		build(mid + 1, r, (rt << 1) | 1);//相当于2*rt+1;                                                                                                                                                                                                 
		pushUp(rt);//计算玩向上返回累加和
	};
	void pushUp(int rt) {
		sum[rt] = sum[rt << 1] + sum[(rt << 1) | 1];//rt<<1|1相当于2*rt+1;
	}
private:
	int MAXN;
	vector<int>arr;//arr维护的是原序列信息从0开始，但是在这里arr从1开始
	vector<int>sum;//模拟线段树维护区间和
	vector<int>lazy;//为累加懒惰信息标记
	vector<int>change;//对应位置的更新值
	vector<bool>update;//为更新懒惰标记
};

2.1区间修改

修改大概可以分为两步：

1.找到这段区间。

2.修改这一区间所有的点

大致流程如下：

1.如果当前区间完全被覆盖在目标区间里将这个区间sum数组的的位置加上（r-l+1)*C

2.如果没有完全覆盖则先下传懒标记

3.如果这个区间的左孩子和目标区间有交集，那么就递归给左孩子分配任务

4.如果这个区间的右孩子和目标区间有交集，则递归分配任务给右孩子。

懒更新： 

在线段树中为了提高效率引入了懒跟新：

1.标记的含义：区间已经被更新过，但是子区间没有被更新过，被更新的信息是什么（区间求和只用记录有没有被访问过，而区间的四则运算等多种操作的问题则要记录是那一种操作）。
这里再引入两个很重要的东西：相对标记和绝对标记

相对标记：指的是可以共存的标记，且打标记的顺序与答案无关，即标记可以叠加。 比如说给一段区间中的所有数字都 + a ，我们就可以把标记叠加一下，比如上一次打了一个 加2 的标记，这一次要给这一段区间 +5 ，那么就把 + 2 的标记变成 + 5

绝对标记：

是指不可以共存的标记，每一次都要先把标记下传，再给当前节点打上新的标记。这些标记不能改变次序，否则会出错。 比如说给一段区间的数字重新赋值，或是给一段区间进行多种操作。

例如：

有了 懒惰标记 这种神奇的东西，我们区间修改时就可以偷一下懒，先修改当前节点，然后直接把信息挂在节点上就可以了！
如下面这棵线段树，当我们要修改区间 [ 1 , 4 ] [1,4][1,4] ，将元素赋值为 1 时，我们可以先找到所有的整个区间都要被修改的节点，显然是储存区间 [1,3] 和 [4,4] 的这两个节点。我们就可以先把 [1,3] 的 sum 改为(3−1+1)∗1=3 ,把 [ 4 , 4 ]  的 sum 改为  (1-1+1)*1=1 ，然后给它们打上值为 1  的懒惰标记，然后就可以了。
这样一来，我们每一次修改区间时只要找到目标区间就可以了，不用再向下递归到叶节点，从而提高了效率。

下传标记
碰到 相对标记 这种容易欺负的小朋友，我们只用打一下懒惰标记就可以了。
但是，遇到 绝对标记 ，或是下文提到的 区间查询 ，简单地打上懒惰标记就明显GG了。毕竟， 懒惰标记 只是简单地在节点挂上一个信息而已，遇到复杂的情况可是不行的啊！
于是，懒惰标记的 下传操作 就诞生了。
顾名思义， 下传标记 就是把一个节点的懒惰标记传给它的左右儿子，再把该节点的懒惰标记删去。
我们先来回顾一下标记的含义：

标记的含义：本区间已经被更新过了，但是子区间却没有被更新过，被更新的信息是什么。

显然，父区间是包含子区间的，也就是对于父区间的标记和子区间是有联系的。在大多数情况下，父区间和子区间的标记是 相同的 。因此，我们可以由父区间的标记推算出子区间应当是什么标记。
注意：以下所说的问题都是指区间赋值，除非有什么特别的申明。
如果要给一个节点中的所有元素重新赋值为 x  ，那么它的儿子也必定要被赋值成 x  。所以，我们直接在子节点处修改  sumsum 值，再把子节点的标记改变一下就可以了（由于区间赋值要用 绝对标记 ，因此当子节点已经有标记时，要先下传子节点的标记，再下传该节点的标记。但是区间赋值会覆盖掉子节点的值，因此在这个问题中，直接修改标记就可以了）

下面是在对应区间加C的代码：

void pushUp(int rt) {//更新父亲的累加和
		sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
	}
	void pushDown(int rt, int ln, int rn) {
		if (update[rt]) {//update方法需要使用
			update[rt << 1] = true;//往下发
			update[rt << 1|1] = true;
			change[rt << 1] = change[rt];
			change[rt << 1 | 1] = change[rt];
			lazy[rt << 1] = 0;//清空左右孩子的懒数组
			lazy[rt << 1 | 1] = 0;
			sum[rt << 1] = change[rt] * ln;//左孩子总和
			sum[rt << 1 | 1] = change[rt] * rn;//右孩子总和
			update[rt] = false;//当前位置已经下发改成false;
		}
		if (lazy[rt]) {
			lazy[rt << 1] += lazy[rt];
			lazy[(rt << 1) | 1] += lazy[rt];
			sum[rt << 1] += lazy[rt] * ln;
			sum[rt << 1 | 1] += lazy[rt] * rn;
			lazy[rt] = 0;
		}
	}
	void add(int L, int R, int C, int l, int r, int rt) {//L和R表示实际要修改的范围 l到r表示实际的范围 rt 表示这个范围
		//的信息我去数组中那个位置去找
		if (L <= l && r <= R) {//懒住
			//修改相关信息
			sum[rt] += C * (r - l + 1);
			lazy[rt] += C;
			return;
		}
		//当前任务躲不掉，无法懒更新，要往下发
		int mid = (l + r) >> 1;
		pushDown(rt, mid - l + 1, r - mid);//先将懒信息下发给左右孩子
		if (L <= mid) {//左孩子需要下发任务
			add(L, R, C, l, mid, rt << 1);
		}
		if (R > mid) {//右孩子需要下发任务
			add(L, R, C, mid + 1, r, rt << 1 | 1);
		}
		pushUp(rt);//更新父亲的累加和
	}

对于add中的参数解释：

1.L，R代表要修改的区间范围

2.l,r 代表实际的范围

3.C要加的值

4.rt表示l到r位置对于的信息在数组的那个位置去拿

对于pushdown方法的解释：

1.包括了update方法的和add的懒操作 

 2.2区间查询

区间查询的和add基本类似：

1.如果当前区间完全被覆盖在目标区间里将对于sum位置的数据返回

2.如果没有完全覆盖则先下传懒标记

3.如果这个区间的左孩子和目标区间有交集，那么就递归给左孩子分配任务

4.如果这个区间的右孩子和目标区间有交集，则递归分配任务给右孩子。

对应代码：

long long query(int L, int R, int l, int r, int rt) {
		if (L <= l && r <= R) {//刚好覆盖这个区间直接在这里面拿值
			return sum[rt];
		}
		int mid = (l + r) >> 1;
		pushDown(rt, mid - l + 1, r - mid);//先将懒信息分配给左右孩子
		long long ans = 0;
		if (L <= mid) {
			ans+=query(L, R, l, mid, rt << 1);
		}
		if (R > mid) {
			ans += query(L, R, mid + 1, r, rt << 1 | 1);
		}
		return ans;
	}

 2.3区间更新

区间更新和区间的修改也是基本类似但也所不同

1.如果某一个区间被设置成对应的数那么该区间的lazy数组中的数据全部置为0

2.如果当前区间懒不住要先下发懒信息给左右孩子在分配任务

具体请看代码：

void Update(int L, int R, int C, int l, int r, int rt) {
		if (L <= l && r <= R) {
			update[rt] = true;//标记已经更新过
			change[rt] = C;
			sum[rt] = C * (r - l + 1);
			lazy[rt] = 0;//清空
			return;
		 }
		//当前任务躲不掉，无法懒更新，要往下发
		int mid = (l + r) >> 1;
		pushDown(rt, mid - l + 1, r - mid);
		if (L <= mid) {
			Update(L, R, C, l, mid, rt << 1);
		}
		if (R > mid) {
			Update(L, R, C, mid + 1, r, rt << 1 | 1);
		}
		pushUp(rt);//更新父亲节点的累加和
	}

对应总代码：

#pragma once 
#include<iostream>
#include<vector>
using std::vector;
using std::cout;
using std::endl;
class SegmentTree {
public:
	SegmentTree(const vector<int>& origin) {
		MAXN = origin.size() + 1;
		arr.resize(MAXN);
		for (int i = 1; i < MAXN; i++) {//arr[0]不用从arr[1]开始
			arr[i] = origin[i - 1];
		}
		sum.resize(MAXN << 2);//相当与MAXN*4；用来支持脑补概念中，某一个范围的累加和信息
		lazy.resize(MAXN << 2);//用来支持脑补概念中，某一个没有在往下的累加和标记
		change.resize(MAXN << 2);
		update.resize(MAXN << 2);

	}
	void build(int l, int r, int rt) {
		if (l == r) {
			sum[rt] = arr[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(l, mid, rt << 1);
		build(mid + 1, r, rt << 1 | 1);//相当于2*rt+1;                                                                                                                                                                                                 
		pushUp(rt);
	};
	void pushUp(int rt) {//更新父亲的累加和
		sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
	}
	void pushDown(int rt, int ln, int rn) {
		if (update[rt]) {//update方法需要使用
			update[rt << 1] = true;//往下发
			update[rt << 1|1] = true;
			change[rt << 1] = change[rt];
			change[rt << 1 | 1] = change[rt];
			lazy[rt << 1] = 0;//清空左右孩子的懒数组
			lazy[rt << 1 | 1] = 0;
			sum[rt << 1] = change[rt] * ln;//左孩子总和
			sum[rt << 1 | 1] = change[rt] * rn;//右孩子总和
			update[rt] = false;//当前位置已经下发改成false;
		}
		if (lazy[rt]) {//下发懒信息
			lazy[rt << 1] += lazy[rt];
			lazy[(rt << 1) | 1] += lazy[rt];
			sum[rt << 1] += lazy[rt] * ln;
			sum[rt << 1 | 1] += lazy[rt] * rn;
			lazy[rt] = 0;
		}
	}
	void add(int L, int R, int C, int l, int r, int rt) {//L和R表示实际要修改的范围 l到r表示实际的范围 rt 表示这个范围
		//的信息我去数组中那个位置去找
		if (L <= l && r <= R) {//懒住
			//修改相关信息
			sum[rt] += C * (r - l + 1);
			lazy[rt] += C;
			return;
		}
		//当前任务躲不掉，无法懒更新，要往下发
		int mid = (l + r) >> 1;
		pushDown(rt, mid - l + 1, r - mid);//先将懒信息下发给左右孩子
		if (L <= mid) {//左孩子需要下发任务
			add(L, R, C, l, mid, rt << 1);
		}
		if (R > mid) {//右孩子需要下发任务
			add(L, R, C, mid + 1, r, rt << 1 | 1);
		}
		pushUp(rt);//更新父亲的累加和
	}
	void Update(int L, int R, int C, int l, int r, int rt) {
		if (L <= l && r <= R) {
			update[rt] = true;//标记已经更新过
			change[rt] = C;
			sum[rt] = C * (r - l + 1);
			lazy[rt] = 0;//清空
			return;
		 }
		//当前任务躲不掉，无法懒更新，要往下发
		int mid = (l + r) >> 1;
		pushDown(rt, mid - l + 1, r - mid);
		if (L <= mid) {
			Update(L, R, C, l, mid, rt << 1);
		}
		if (R > mid) {
			Update(L, R, C, mid + 1, r, rt << 1 | 1);
		}
		pushUp(rt);//更新父亲节点的累加和
	}

	
	long long query(int L, int R, int l, int r, int rt) {
		if (L <= l && r <= R) {//刚好覆盖这个区间直接在这里面拿值
			return sum[rt];
		}
		int mid = (l + r) >> 1;
		pushDown(rt, mid - l + 1, r - mid);//先将懒信息分配给左右孩子
		long long ans = 0;
		if (L <= mid) {
			ans+=query(L, R, l, mid, rt << 1);
		}
		if (R > mid) {
			ans += query(L, R, mid + 1, r, rt << 1 | 1);
		}
		return ans;
	}
private:
	int MAXN;
	vector<int>arr;//arr维护的是原序列信息从0开始，但是在这里arr从1开始
	vector<int>sum;//模拟线段树维护区间和
	vector<int>lazy;//为累加懒惰信息标记
	vector<int>change;//对应位置的更新值
	vector<bool>update;//为更新懒惰标记
};

上述代码博主经过测试基本正确如有错误请在评论区留言！

26 4 0
文章推荐： WebGPU 的几个最佳实践
文章推荐： 下一代的 3D Tiles 前瞻
文章推荐： 大前端JS篇之搞懂【WeakSet】
文章推荐： WebGL 与 WebGPU 比对[2] - 初始化篇
知者
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com