【题解】简易数字变换(线段树)
本文最后更新于 80 天前,其中的信息可能已经有所发展或是发生改变。

区间求和问题,需要使用RMQ算法。常见的RMQ算法有ST算法和线段树。ST算法适用于离线操作,本题中还需要对某一下标范围内的数字都加上一个给定的值,所以使用线段树。

线段树的基本思想是分治,每一个节点存储的是一段区间的结果。(如图1,展示的是1~8区间)一颗线段树具有插入、修改、查询三个基本功能。

图1

线段树中的节点在内存中都是连续的,那如何找到一个节点的子节点呢?以图1中[1,4]节点为例,该节点编号为4,该节点的子节点编号为8和9。我们可以发现,左子节点的编号是父节点编号*2。事实上,对于[a,b]编号为n的节点,它的左子节点[a,(a+b)/2]编号为2*n,右子节点[(a+b)/2+1,b]编号为2*n+1。

有了对节点的初步认识后,我们就可以建树了。在本题中,结构体内存放两个数据,value和lazy。值得注意的是,创建结构体数组时,结构体个数为4*MAXN(至于为什么是4,后面会讲到)

void build(int l, int r, int p)
{
	if (l == r)当节点的左右范围相等时,我们就可以认为它到根部了
	{
		scanf("%lld", &tree[p].v);
		return;
	}
	int mid = (l + r) / 2;
	build(l, mid, p * 2);
	build(mid + 1, r, p * 2 + 1);
	tree[p].v = tree[p * 2].v + tree[p * 2 + 1].v;//父节点的值=左节点+右节点
}

接下来就是查询了,图2演示了对于区间[4,7]的查询过程。蓝色节点是被查询的节点。

整个查询过程,就是判断左右子节点是否在查询范围内,如果在,就进入,如果不在,就停止。如果该节点完全包含在被查询区域内,就直接返回结果,不需要进入子节点(线段树省时的原因就在这里)如果只有其中一个子节点在查询范围内,就只进入该节点。(例如5号节点[3,4],只进入了右节点)

int query(int l, int r,int x, int y,int p)
{
	if (l <= x && y <= r)return tree[p];//如果该节点完全包含在被查询区域内,就返回结果。
	int mid = (x + y) / 2;
	if (r <= mid)return query(l, r, x, mid, p * 2);//只进入左节点
	if (mid<l)return query(l, r, mid + 1, y, p * 2 + 1);//只进入右节点
	return max(query(l, mid, x, mid, p * 2), query(mid + 1,r, mid + 1, y, p * 2 + 1));//左右两个节点都进入
}

接下来就是重点,如果去修改节点的值。它的复杂之处在于,上层节点的结果来自于根部节点,我们不能只去修改根部节点而不去更新上层节点,也不能只更新上层节点而不修改根部节点。但是全部更新一遍太麻烦了,又耗时,所以我们引入了lazy tag。

Lazy tag的原理是,我们在对一段区间做操作时,可以先不更新子节点,而是先把这个结果存在父节点lazy变量里,等到查询到这个节点的时候,再去更新子节点的值。这样可以节省很多不必要的更新操作,因为可能不是所有被修改的区间都被查询到,而且全部更新一遍非常耗时,还可以实现缓存(多次对一段区间做操作可以合并为一次更新)

例如对区间[2,7]都加上5,3~6的根节点没有被更新,只更新了[3,4][5,6]两个节点。(图3)

void update(int l, int r, int x, int y, int p, int num)
{
	if (l <= x && y <= r)//当前区间完全包含在被更新区间时就不再向子节点更新
	{
		tree[p].v += (y - x + 1) * num;
		tree[p].lazy += num;
		return;
	}
	if (tree[p].lazy)push_down(x, y, p);//如果当前节点lazy值不为0,就说明已经有值缓存在lazy中了,子节点必须先更新
	int mid = (x + y) / 2;
	if (l <= mid)update(l, r, x, mid, p * 2, num);
	if (mid < r)update(l, r, mid + 1, y, p * 2 + 1, num);
	tree[p].v = tree[p * 2].v + tree[p * 2 + 1].v;
}

在查询的时候,和前文提到的方式类似,唯一的区别在于当该节点lazy值不为0时,就要先把lazy的值加到两个子节点上再进行查询。

ll query(int l, int r, int x, int y, int p)
{
	if (l <= x && y <= r)return tree[p].v; //当前区间完全包含在被查询区间时就直接返回结果
	if (tree[p].lazy)push_down(x, y, p);// 如果当前节点lazy值不为0,就说明已经有值缓存在lazy中了,子节点必须先更新
	int mid = (x + y) / 2;
	ll ans = 0;
	if (l <= mid)ans += query(l, r, x, mid, p * 2);
	if (mid < r)ans += query(l, r, mid + 1, y, p * 2 + 1);
	return ans;
}

建树,查询,修改到此就结束了,接下来回到之前的问题,为什么开数组/结构体的时候要乘4倍呢?

可以发现,第3层已经出现了区间为1的节点了([3,3],[4,4],[5,5]),但是还有两个区间为的节点在第4层。那第4层其它的节点可以省略吗?答案是不能。

图5中[3,3]没有子节点,但是这两个节点必须留着,否则会影响到[4,5]的子节点。
相同层数的线段树使用的节点数都是一样的,都是$2^{n+1}-1$个。例如[1,5]和[1,6]都是4层,需要15个节点。
[1,[$2^{n-1}+1$,$2^{n}$]]的线段树层数相同,使用的节点数相同,均为$2^{n+1}-1$个。
所以可以发现,[1,$2^{n-1}+1$]剩下的节点数最多,使用的节点数为自身数量的$\frac{2^{n+1}-1}{2^{n-1}+1}$约等于4倍。

文章标题:【题解】简易数字变换(线段树)
文章链接:https://intmain0.com/213/
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处
评论和私信会在第一时间回复。如果您觉得文章对您有帮助,可以点击文章右下角【分享】一下。您的鼓励是博主的最大动力!
暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇