「学习笔记」线段树

这篇具有很好参考价值的文章主要介绍了「学习笔记」线段树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

介绍:

线段树是一棵二叉搜索树,思想与分治很想,把一段区间平分平分再平分,平分到不能平分为止,可以进行方便的区间修改和区间查询,当然,树状数组能做的单点修改、单点查询,线段树也可以更好地实现,总之,线段树是树状数组的升级版,此外,线段树能做的平衡树也能做,但平衡树码量太大,考场上一般写不出来反正我是写不出来,就是会写也不会用,其次有些特殊的线段树如权值线段树也可以水过平衡树,可见,线段树的应用还是十分广泛的。
图片来自 \(\texttt{OI-Wiki}\)

建树:

一般的线段树都是递归建树,当然,也有一种不用递归建树的线段树,即非递归线段树——zkw 线段树
当然,zkw 线段树并不是我们现在的主角,我们讲一下递归建树的操作
首先,可以设置三个方便的宏定义偷懒

typedef long long ll;
#define ls (p << 1)
#define rs (p << 1 | 1)
#define mid ((l + r) >> 1)
// ls 左儿子 rs 右儿子 mid 中间值

因为线段树是棵二叉树,\(p\) 是当前节点的编号,所以一个结点的左儿子和右儿子可以表示为\(p \times 2\)\(p \times 2 + 1\),用位运算速度更快,但是要注意运算符之间的优先级,不熟悉的那就勤加括号吧反正加几个括号基本没影响,还不容易出错,不加白不加,至于这个 \(mid\),纯粹是图省事
刚才我们也讲了左右儿子的表示方法,所以我们的空间要开到原来的四倍,当然,线段树还有一种结构体存法,那个存法开两倍空间即可,但要维护的东西不少,所以也没剩多少空间,而且操作起来很麻烦,不如用这种左右儿子表示法来存储

ll val[N << 2];

「学习笔记」线段树

如图,这是一颗线段树,每一个节点都代表着一个区间的信息,如 \(1\) 号节点代表着区间 \([1, 5]\)的和,\(4\) 代表着区间 \([1, 2]\) 的和,我们发现它是从中间值平分开的,这里就是分治的思想,二分,每部分在自己递归,最后再合并一下,上代码

void build(int p, int l, int r) {
	if (l == r) {
		val[p] = read();
		return ;
	}
	build(ls, l, mid);
	build(rs, mid + 1, r);
	pushup(p);
}

代码也不是很长,宏定义是个好东西
对于 pushup 函数,你可能会想知道这是什么东西,别急,这就是接下来我们要讲的

更新函数

更新函数,说白了就是将两个儿子的信息合并,合并的方式有多种,相加、相乘、取最值、dp 等等,具体题目具体分析,这里就展示一下相加类型的更新函数,要记住,建树和修改操作等一些操作,一定不要忘记更新!!!

void pushup(int p) {
	val[p] = val[ls] + val[rs];
}

到这里,建树部分才算正式完成,接下来就是各种操作了

众所周知,线段树对于区间操作那可是十分厉害的,虽然树状数组也能实现区间操作,但是太麻烦,还要背公式,相对于线段树也不好理解,因此对于区间操作,一般都用线段树,还有一个东西叫分块,也是可以的当然并不是主角

区间修改

还是刚刚的图
「学习笔记」线段树
修改区间 \([1 , 5]\),在线段树上,\([1 , 5]\) 可以由 \([1, 4], [5, 5]\) 组成,在这里我们可以看出,当一段小区间属于这个修改的大区间时,我们可以直接对这个小区间进行操作,不必继续向下修改,但如果后面又对这个小区间中的更小的区间,如\([3, 3]\)进行修改,然后要查询它的值怎么办呢?这里我们要引入一个新的变量——\(lazy\),俗称懒标记。
线段树中的每一个元素都需要一个懒标记,所以它也要开到源数据的\(4\)

ll lazy[N << 2];

懒标记,由名得知,它很懒,为什么?因为它懒得继续向下一个一个元素修改,但判断这个区间全部属于要修改的大区间时,直接对着对当前节点进行标记,同时 \(lazy\) 负责记录对这个区间的操作,节省时间由此可以看出,懒也有懒的好处,它的含义是对当前节点的区间中所有的元素都进行一个操作,\(lazy\)也有很多类型,有的负责记录区间加减,有的负责记录区间乘除,还有负责乘方开方、是否异或等等,设置 \(lazy\) 的含义在一些题目当中也是一个难点,具体题目具体分析,在区间修改中,\(lazy\) 主要也是为了省时,这里以区间加减的修改函数为例

void change(int p, int l, int r, int lr, int rr, ll v) {
	if (lr <= l && r <= rr) {
		lazy[p] += v;
		val[p] += v * (r - l + 1);
		return ;
	}
	pushdown(p, l, r);
	if (lr <= mid) {
		change(ls, l, mid, lr, rr, v);
	}
	if (rr > mid) {
		change(rs, mid + 1, r, lr, rr, v);
	}
	pushup(p);
}
// l、r 当前节点所对应的区间 lr、rr 要修改的区间的左右边界 v 区间要加减的数

向下递归过程中,如果现在节点对应的区间 \([l, r]\) 已经被修改区间 \([lr, rr]\)包含,直接对当前节点进行操作,具体操作如代码所示,很好理解,不细说,\(lazy\) 加上 \(v\),代表这段区间整体加上 \(v\),如果有不属于\([lr, rr]\)的部分,分治,如果 \(lr\) 小于等于中间值,说明在当前对应区间的左半段有要进行修改操作的,向左孩子递归,\(rr\) 大于中间值,说明在当前对应区间的右半段也又要修改操作的,向右孩子递归,最后,不要忘记更新!,至于 pushdown 操作,这就和我们的 \(lazy\) 有关了,我们存下 \(lazy\),但是 \(lazy\) 到底在哪里有作用呢,这就引出了我们的

下传函数和区间查询

为了方便,我们一起将!区间查询这个操作,字面意思,就是个查询操作,但怎么查询才能更快呢,先上图
「学习笔记」线段树
假设,我们要查询区间[1, 5]的所有数的和,那我们只需要查询 \(1\) 号节点的数值就行了,\(1\) 号节点存储着区间 \([1, 5]\) 的和,所以,查询操作与修改操作有着一样的思路,遇到全属于大区间的小区间,直接返回小区间的值就行了
但这里有个问题,假设我们已经对区间 \([1, 2]\) 都加上了 \(v\),按照我们的修改操作,直接对 \(4\) 号节点进行更新,记录 \(lazy\),那我现在要查询区间 \([1, 1]\),即 \(8\) 号节点的信息怎么办,当初的修改操作压根就没递归到这一层,这时候,\(lazy\) 就派上用场了,还记得 \(lazy\) 的含义吗?对区间内所有的元素都进行一个操作,那么,我们是否可以把这个 \(lazy\) 下传给左右儿子呢?反正左右儿子都是属于这个区间的,这个修改也是对它们的修改,所以下传这个 \(lazy\) 没有什么影响,那我们就下传,这里就是加减操作的下传函数的代码。

void pushdown(int p, int l, int r) {
	if (!lazy[p])	return ; // 没有lazy还下传个毛线
	lazy[ls] += lazy[p], val[ls] += lazy[p] * (mid - l + 1);
	lazy[rs] += lazy[p], val[rs] += lazy[p] * (r - mid);
	lazy[p] = 0; // 下传完了,它的lazy也就没了
}

查询要下传,为什么修改也要下传呢?当然是因为修改函数中有 pushup 函数,最后一更新,本来已经修改好的正确答案会被更新掉,如果下传了 \(lazy\),那么更新后还是原来的正确答案,否则,最后会被错误答案代替,现在解决了 \(lazy\) 的问题,我们也就可以开心的进行区间查询了,上代码。

ll query(int p, int l, int r, int lr, int rr) {
	if (lr <= l && r <= rr) {
		return val[p];
	}
	pushdown(p, l, r);
	ll ans = 0;
	if (lr <= mid)	ans += query(ls, l, mid, lr, rr);
	if (rr > mid)	ans += query(rs, mid + 1, r, lr, rr);
	return ans;
}

区间操作就讲这么多,具体还是 \(lazy\) 与下传、更新函数的操作,具体题目具体分析

前面说了,树状数组能做的线段树都能做,那么树状数组的单点修改、单点查询在线段树上是 so easy 的,都是递归,没什么技术含量,只需 change 函数的 \(lr, rr\) 都设成要修改的位置,就完成了,query 函数是一样的,当然也可以自己再写个函数,下面给个例子

void update(int p, int l, int r, int x, ll v) {
	if (l == r) {
		val[p] += v;
		return ;
	}
	if (x <= mid) {
		update(ls, l, mid, x, v);
	}
	else update(rs, mid + 1, r, x, v);
	pushup(p);
}

ll query(int p, int l, int r, int x) {
	if (l == r) {
		return val[p];
	}
	if (x <= mid)	return query(ls, l, mid, x);
	else	return query(rs, mid + 1, r, x);
}

真的毫无技术含量

其他

\(lazy\) 方面,有一种优化方法叫标记永久化
标记永久化:如果确定懒惰标记不会在中途被加到溢出(即超过了该类型数据所能表示的最大范围),那么就可以将标记永久化。标记永久化可以避免下传懒惰标记,只需在进行询问时把标记的影响加到答案当中,从而降低程序常数。具体如何处理与题目特性相关,需结合题目来写。这也是树套树和可持久化数据结构中会用到的一种技巧。——\(\text{OI wiki}\)
空间方面,有动态开点优化,可以与权值线段树搭配
线段树方面,还有一些其他的线段树,如权值线段树、zkw 线段树。
权值线段树,叶节点代表的不再是区间范围,而是权值,非叶节点代表的是权值区间而不是我们原本的区间,加上动态开点,可以水过洛谷的普通平衡树
zkw线段树,先%为敬,非递归线段树,因为不递归,跑的是真的很快,但是不好理解,其次在竞赛中,初学者是真的不会用这个去做题,所以对像我这样的蒟蒻而言,也就拿它玩玩,水水模板,然后就吃灰了,这里给出洛谷普通线段树 \(1\) 的 zkw 线段树代码

zkw 线段树
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e5 + 5;

int n, num = 1, m;
ll tree[N << 2], delta[N << 2];

inline ll read() {
	ll x = 0;
	int fg = 0;
	char ch = getchar();
	while (ch < '0' || ch > '9') {
		fg |= (ch == '-');
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = (x << 3) + (x << 1) + (ch ^ 48);
		ch = getchar();
	}
	return fg ? ~x + 1 : x;
}

void print(ll x, char y) {
	cout << x;
	putchar(y);
}

void build() {
	for (; num <= n + 1; num <<= 1);
	for (int i = num + 1; i <= num + n; ++ i) {
		tree[i] = read();
	}
	for (int i = num - 1; i >= 1; -- i) {
		tree[i] = tree[i << 1] + tree[i << 1 | 1];
	}
}

void change(int l, int r, ll v) {
	int lNum = 0, rNum = 0, nNum = 1;
	for (l = num + l - 1, r = num + r + 1; l ^ r ^ 1; l >>= 1, r >>= 1, nNum <<= 1) {
		tree[l] += v * lNum;
		tree[r] += v * rNum;
		if (~l & 1) {
			delta[l ^ 1] += v;
			tree[l ^ 1] += v * nNum;
			lNum += nNum;
		}
		if (r & 1) {
			delta[r ^ 1] += v;
			tree[r ^ 1] += v * nNum;
			rNum += nNum;
		}
	}
	for (; l; l >>= 1, r >>= 1) {
		tree[l] += v * lNum;
		tree[r] += v * rNum;
	}
}

ll query(int l, int r) {
	int lNum = 0, rNum = 0, nNum = 1;
	ll ans = 0;
	for (l = num + l - 1, r = num + r + 1; l ^ r ^ 1; l >>= 1, r >>= 1, nNum <<= 1) {
		if (delta[l]) {
			ans += delta[l] * lNum;
		}
		if (delta[r]) {
			ans += delta[r] * rNum;
		}
		if (~l & 1) {
			ans += tree[l ^ 1];
			lNum += nNum;
		}
		if (r & 1) {
			ans += tree[r ^ 1];
			rNum += nNum;
		}
	}
	for (; l; l >>= 1, r >>= 1) {
		ans += delta[l] * lNum;
		ans += delta[r] * rNum;
	}
	return ans;
}

int main() {
	n = read();
	m = read();
	build();
	for (int op, x, y, i = 1; i <= m; ++ i) {
		op = read(), x = read(), y = read();
		if (op == 1) {
			ll v = read();
			change(x, y, v);
		}
		else {
			print(query(x, y), '\n');
		}
	}
	return 0;
}

其他方面的这些东西,有些很有用,有些也就图一乐,以后如果学会了,我会来补坑的。
标记永久化:「学习笔记」线段树标记永久化
可持久化线段树(权值线段树):「学习笔记」可持久化线段树文章来源地址https://www.toymoban.com/news/detail-471051.html

到了这里,关于「学习笔记」线段树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】二叉搜索树——二叉搜索树的概念和介绍、二叉搜索树的简单实现、二叉搜索树的增删查改

      二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树:   (1)若它的左子树不为空,则左子树上所有节点的值都小于根节点的值   (2)若它的右子树不为空,则右子树上所有节点的值都大于根节点的值   (3)它的左右子树也分别为二叉

    2024年02月09日
    浏览(28)
  • Java——二叉树的最近公共祖先及二叉搜索树介绍

    目录 二叉树的最近公共祖先 题目  思路一:如果给定的是一颗二叉搜索树, 思路二:假设是孩子双亲表示法  二叉搜索树 定义Node类 查找 删除 插入 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点

    2023年04月08日
    浏览(24)
  • leetcode做题笔记98. 验证二叉搜索树

    给你一个二叉树的根节点  root  ,判断其是否是一个有效的二叉搜索树。 有效  二叉搜索树定义如下: 节点的左子树只包含  小于  当前节点的数。 节点的右子树只包含  大于  当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 本题要判断二叉树是否为二叉

    2024年02月11日
    浏览(27)
  • leetcode做题笔记96. 不同的二叉搜索树

    给你一个整数  n  ,求恰由  n  个节点组成且节点值从  1  到  n  互不相同的  二叉搜索树  有多少种?返回满足题意的二叉搜索树的种数。 本题与上题近似,只需分别考虑左右子树,即f[j-1]*f[i-j]得到状态方程,最后输出f[n[即可,或者直接使用公式,二叉搜索树的种数与

    2024年02月11日
    浏览(22)
  • leetcode做题笔记95. 不同的二叉搜索树 II

    给你一个整数  n  ,请你生成并返回所有由  n  个节点组成且节点值从  1  到  n  互不相同的不同  二叉搜索树   。可以按  任意顺序  返回答案。 本题要列出所有二叉搜索树,即可转换为列举左子树所有集合和右子树所有集合两个问题,分别用递归函数将左右子树根节

    2024年02月11日
    浏览(23)
  • 【C++ 学习 ⑳】- 详解二叉搜索树

    目录 一、概念 二、实现 2.1 - BST.h 2.2 - test.cpp 三、应用 四、性能分析   二叉搜索树(BST,Binary Search Tree) ,又称 二叉排序树 或 二叉查找树 。 二叉搜索树是一棵二叉树,可以为空;如果不为空,满足以下性质: 非空左子树的所有键值小于其根节点的键值 非空右子树的所有

    2024年02月09日
    浏览(24)
  • 华为OD机试 - 最少数量线段覆盖 - 二叉树(Java 2023 B卷 100分 考试抽中题)

    华为OD机试 2023B卷题库疯狂收录中,刷题 点这里

    2024年02月11日
    浏览(35)
  • 【数据结构】平衡二叉搜索树(AVL树)——AVL树的概念和介绍、AVL树的简单实现、AVL树的增删查改

      为什么要引入平衡二叉搜索树?   在之前我们学习了二叉搜索树,二叉搜索树的结构类似于一个倒置的树,而左子树的值小于根节点的值,右节点的值大于根节点的值,这种结构使得二叉搜索树在处理有序数据时非常高效。但是如果 在传入的数据为有序或接近有序,

    2024年02月07日
    浏览(33)
  • 思通舆情 是一款开源免费的舆情系统 介绍

    思通舆情 是一款开源免费的舆情系统。 支持本地化部署,支持在线体验。 支持对海量舆情数据分析和挖掘。 无论你是使用者还是共同完善的开发者,欢迎 pull request 或者 留言对我们提出建议。 您的支持和参与就是我们坚持开源的动力!请   star 或者 fork! 思通舆情 的功能

    2024年04月13日
    浏览(48)
  • 数据结构学习记录——判断是否为同一颗二叉搜索树(题意理解、求解思路、程序搭建框架、具体函数的实现)

    目录 题意理解 问题 描述 输入样例  输出样例 求解思路 建两棵二叉树 不建树 建一棵树 搜索树表示 程序框架搭建 如何建搜索树 如何判别 方法 查找函数 判断函数 其他函数 给定一个插入序列就可以唯一确定一颗二叉搜索树。 但是,一颗给定的二叉搜索树却可以由多种不同

    2024年02月02日
    浏览(30)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包