首页 > 其他分享 >线段树

线段树

时间：2023-08-16 22:24:21浏览次数：37  
标签：int sum tr 节点 add mul 线段

  • 线段树 \(1.0\)

线段树 \(1.0\) 可以实现对区间内的数加减，查询区间和的操作。

例题

【模板】线段树 1

原理

定义

l,r ：分别表示节点表示的区间的左端点与右端点。

sum ：节点表示的区间 \([l,r]\) 内数组元素之和。

add ：lazy 标记，表示这个节点以下的 所有子节点中的叶子 表示的数在计算时都应加上 lazy 标记的值。

tr[i] ：表示第 \(i\) 个节点，如果 tr[i] 是叶子节点，那么它表示数组中的一个数。

向上更新

将子节点记录的区间和更新到自己的区间和上。

向下更新

如果自己的 lazy 值不为 \(0\)，那么就让子节点的区间和与 lazy 值分别加上自己的区间和（属于子节点部分的）与 lazy 值。

创建节点

当且仅当 \(l=r\) 的时候，节点是叶子节点。如果是叶子节点则直接返回，否则将当前节点分裂成两个子节点。递归创建左子树与右子树，创建完左子树与右子树之后返回来更新区间和。

修改节点（加法）

点修改：从根节点进入，递归找到要被修改的叶子，把该节点的值增加要修改的值。然后从下往上更新其祖先节点上的统计值。

区间修改：当 \([x,y]\) 完全覆盖节点区间的时候，先修改该节点表示的区间和，再在它上面打上 lazy 标记，并立即返回。

如果查询操作或修改操作面向某个拥有 lazy 标记的节点的整个区间，那么不对这个 lazy 标记作任何操作；如果查询操作或修改操作需要操作某个拥有 lazy 标记的节点的部分区间，那么就向下调整，让它的子节点“继承”这个节点的 lazy 值。
换言之，lazy 标记是否下传取决于当前节点的表示的区间是否能够被待修改区间完全覆盖。

e.g. 对于某个节点，其表示区间 \([10,20]\)，如果要将 \([5,25]\) 内的元素全部增加 \(k\)，那么不需要对其 lazy 值作任何操作。如果要查询或者修改区间 \([12,18]\) 或者 \([15,25]\) 内数的值，那么就需要下传 lazy 标记，向下调整后再进行查询或者修改操作。

查询区间和

从根节点进入。若查询区间 \([x,y]\) 完全覆盖当前节点表示的区间，那么立即回溯，并返回该节点的 \(sum\) 值。否则，若左子节点表示的区间与 \([x,y]\) 右重叠，则递归访问左子树；若右子节点表示的区间与 \([x,y]\) 右重叠，则递归访问右子树。（左右子树的访问不互斥）

代码

#include <iostream>
#define int long long
using namespace std;
const int N = 1000005;
int n, w[N];//分别表示数组长度和待输入数组
struct NODE
{
	int l, r, sum, add;//表示节点表示的区间左端点，右端点，区间内的和，“懒”标记
	//当且仅当节点为叶子的时候，节点表示数组中的某个数
	//“懒”标记的意义是，某个节点下的所有子节点中的叶子表示的数，实际值+“懒”标记的值
}tr[4 * N];//开4倍空间
void pushup(int p)//向上更新
{
	tr[p].sum = tr[2 * p].sum + tr[2 * p + 1].sum;
}
void pushdown(int p)//向下更新
{
	if (tr[p].add)
	{
		tr[2 * p].sum += tr[p].add * (tr[2 * p].r - tr[2 * p].l + 1);
		tr[2 * p + 1].sum += tr[p].add * (tr[2 * p + 1].r - tr[2 * p + 1].l + 1);
		tr[2 * p].add += tr[p].add;
		tr[2 * p + 1].add += tr[p].add;
		tr[p].add = 0;
	}
}
void build(int p, int l, int r)//p表示节点的编号，最终目的是通过dfs找到叶子节点
{
	tr[p] = { l,r,w[l],0 };
	if (l == r)return;//如果是叶子节点则返回
	//否则将当前节点分裂
	int m = (l + r) / 2;
	build(2 * p, l, m);
	build(2 * p + 1, m + 1, r);
	pushup(p);//创建完左子树与右子树之后返回来更新sum值
}
void update(int p, int x, int k)//对x位置上的数加上k
{
	if (tr[p].l == x && tr[p].r == x)//是叶子则修改
	{
		tr[p].sum += k;
		return;
	}
	int m = (tr[p].l + tr[p].r) / 2;
	if (x <= m)update(2 * p, x, k);
	else update(2 * p + 1, x, k);
	pushup(p);
}
void update(int p, int x, int y, int k)//对区间[x, y]内的数都加上k
{
	if (x <= tr[p].l && tr[p].r <= y)//覆盖则修改
	{
		tr[p].sum += (tr[p].r - tr[p].l + 1) * k;
		tr[p].add += k;
		return;
	}
	int m = (tr[p].l + tr[p].r) / 2;
	pushdown(p);
	if (x <= m)update(2 * p, x, y, k);
	if (y >= m + 1)update(2 * p + 1, x, y, k);
	pushup(p);
}
int query(int p, int x, int y)//区间查询
{
	if (x <= tr[p].l && tr[p].r <= y)//覆盖则返回
	{
		return tr[p].sum;
	}
	//不覆盖则分别查询其左子树与右子树
	int m = (tr[p].l + tr[p].r) / 2;
	pushdown(p);
	int sum = 0;
	if (x <= m)sum += query(2 * p, x, y);
	if (y >= m + 1) sum += query(2 * p + 1, x, y);
	return sum;
}
signed main()
{
	ios::sync_with_stdio(0);
	int m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)cin >> w[i];
	build(1, 1, n);
	for (int i = 1; i <= m; i++)
	{
		int op;
		cin >> op;
		if (op == 1)
		{
			int x, y, k;
			cin >> x >> y >> k;
			update(1, x, y, k);
		}
		else
		{
			int x, y;
			cin >> x >> y;
			cout<<query(1, x, y)<<endl;
		}
	}
	return 0;
}

  • 线段树 \(2.0\)

相比于线段树 \(1.0\)，线段树 \(2.0\) 支持对区间内作乘法的操作。

例题

【模板】线段树 2

原理

定义

（新增定义：针对乘法的 lazy 标记值 \(mul\)）

mul ：\(lazy\) 标记，表示这个节点以下的 所有子节点中的叶子 表示的数在计算时都应乘上 lazy 标记的值。

（以下操作与线段树 \(1.0\) 有区别）

向下更新

在向下更新时，因为有乘法操作的存在，发生更新操作的判断条件应该由 tr[p].add != 0 变为 tr[p].add != 0 || tr[p].mul != 1。与此同时，满足更新条件的节点的子节点的区间和不仅仅需要“继承”父节点的 \(add\)，还要继承其 \(mul\)；子节点的 \(addd\) 与 \(mul\) 同样需要由父节点继承而来。

我们着重关注子节点的继承顺序：首先，“先乘后加”的顺序是可行的。在子节点区间和继承父节点的 \(add\) 与 \(mul\) 时，子节点应先乘上父节点的 \(mul\) 值，再加上父节点的 \(add\) 值与子节点区间的长度之积。在子节点的 \(add\) 与 \(mul\) 继承父节点的时候，子节点的 \(add\) 应首先乘上父节点的 \(mul\)，再加上父节点的 \(add\)，而子节点的 \(mul\) 应乘上父节点的 \(mul\)。

以左子节点继承为例：

void test(int p)
{
	if (tr[p].add != 0 || tr[p].mul != 1)
	{
		tr[2 * p].sum = (tr[p].mul * tr[2 * p].sum) % mod;
		tr[2 * p].sum = (tr[2 * p].sum + tr[p].add * (tr[2 * p].r - tr[2 * p].l + 1)) % mod;

		tr[2 * p].add = (tr[2 * p].add * tr[p].mul) % mod;
		tr[2 * p].add = (tr[2 * p].add + tr[p].add) % mod;
		tr[2 * p].mul = (tr[2 * p].mul * tr[p].mul) % mod;

		tr[2 * p].sum %= mod;
		tr[2 * p].mul %= mod;
		tr[p].add = 0;
		tr[p].mul = 1;
	}
}

关于这么做的原因，实际上它与作乘法时的 multiple 操作是相呼应的。对于正确性的证明放在原理部分末尾。

修改节点（区间乘法）

当我们对一个区间作乘法的时候（假定乘 \(k\)），整个区间的区间和当然会乘 \(k\)，同时我们要让这个区间对应的节点的 \(mul\) 值乘 \(k\)。此外，这个节点的 \(add\) 值也应乘 \(k\)。

正确性的证明

（以下为叙述简便，设父节点表示区间的长度为 \(l\)）

我们考虑在输出区间和时每一个元素的计算方式。由定义，每一个元素存储在叶子节点。如果某个节点表示的区间可以被查询区间完全覆盖，那么计算这个子区间和的时候就会直接返回这个节点上面的区间和。而由于 \(add\) 和 \(mul\) 的存在，我们可以暂缓更新某个节点的子节点的信息，直到有操作需要详细地访问这个区间的某一部分。这一段是对上面思路的一部分总结。

在需要用父节点的 \(add_0\) 和 \(mul_0\) 更新子节点的时候，设子节点的区间和为 \(sum\)，那么子节点可以用\(sum \times mul_0 + add_0\) 来更新，这是因为在乘法操作时，父节点的 \(add_0\) 已经由 \(add_0 \times mul_0\) 更新。

我们首先考虑一次加法与一次乘法混合的情况。

如果是先做乘法，那么 \(add_0\) 变为原来的 \(k\) 倍，\(mul_0\) 变为原来的 \(k\) 倍，再做加法使 \(add_0\) 加 \(t\)。记 \(mul_1 = mul_0 \times k\)，\(add_1 = add_0 + t\)。在利用父节点的 lazy 值更新子节点的时候，子节点现在的区间和 $sum^{\prime} = sum \times mul_1 + add_1 \times l \(，而\)sum \times mul_1 + add_1\times l = sum \times mul_0 \times k + add_0\times l \times k + t$。与 \(k \times (sum \times mul_0 + add_0\times l )+ t\) ，它们显然是等价的。

而如果是先做加法，则 \(add_0\) 先加 \(t\)，然后做乘法使现在的 \(add_0\) 变为原来的 \(k\) 倍，\(mul_0\) 变为原来的 \(k\) 倍
\(add_0\) 变为原来的 \(k\) 倍，\(mul_0\) 变为原来的 \(k\) 倍。此时记 \(mul_ 1 = mul_0\times k\)，\(add_1 = (add_0 + t) \times k\)。在利用父节点的 lazy 值更新子节点的时候，子节点现在的区间和 \(sum^{\prime} = sum \times mul_1 + add_1\times l\)，而\(sum \times mul_1 + add_1\times l = sum \times mul_0 \times k + (add_0 + t)\times l \times k\)，这与 \(k \times (sum \times mul_0 + (add_0 +t)\times l)\) 也显然是等价的 。

对于多次的加法与乘法混合，显然，如果是连续的加法或连续的乘法，它们等价于一次加法或一次乘法。所以任何加法与乘法混合的运算都等价于交替出现的加法与乘法。

由于一次加法、一次乘法 以及 一次加法混合一次乘法 都不会使父节点的 lazy 值更新子节点的区间和的过程发生改变，所以对于交替的加法与乘法，它们要么可以分为若干次一次加法混合一次乘法，要么可以分为若干次一次加法混合一次乘法 加 一次加法，要么可以分为若干次一次加法混合一次乘法 加 一次乘法。对于这三种情形中的每一种，其中的每一步都不会改变更新过程，所以这三种情形下的操作都不会改变更新过程。

不能在继承父节点的时候先加后乘的原因

如果继承父节点的过程是 \(sum^{\prime} = (sum+add_1\times l)\times mul_1\)，那么在父节点执行加法操作时（以加 \(k\) 为例），从结果上看，\(sum^{\prime} = (sum+add_0\times l)\times mul_1+k\)，那么实际上对于加法的 \(lazy\) 值，只有当 \(add_1 = add_0+\frac{k}{mul_1}\) 才能满足 \(sum^{\prime} = (sum+add_1\times l)\times mul_1\) 这个过程。但是 \(\frac{k}{mul_1}\) 涉及除法，可能会丢失精度，不如先乘后加。

代码

#include <iostream>
#define int long long
using namespace std;
const int N = 1000005;
int n, w[N];//分别表示数组长度和待输入数组
int mod;//表示模数
struct NODE
{
	int l, r, sum, add, mul;
	//和作加法的“懒”标记类似，mul是作乘法的“懒”标记
}tr[4 * N];//开4倍空间
void pushup(int p)//向上更新
{
	tr[p].sum = (tr[2 * p].sum + tr[2 * p + 1].sum) % mod;
}
void pushdown(int p)//向下更新
{
	if (tr[p].add != 0 || tr[p].mul != 1)
	{
		tr[2 * p].sum = (tr[p].mul * tr[2 * p].sum) % mod;
		tr[2 * p].sum = (tr[2 * p].sum + tr[p].add * (tr[2 * p].r - tr[2 * p].l + 1)) % mod;
		tr[2 * p + 1].sum = (tr[2 * p + 1].sum * tr[p].mul) % mod;
		tr[2 * p + 1].sum = (tr[2 * p + 1].sum + tr[p].add * (tr[2 * p + 1].r - tr[2 * p + 1].l + 1)) % mod;

		tr[2 * p].add = (tr[2 * p].add * tr[p].mul) % mod;
		tr[2 * p + 1].add = (tr[2 * p + 1].add * tr[p].mul) % mod;
		tr[2 * p].add = (tr[2 * p].add + tr[p].add) % mod;
		tr[2 * p + 1].add = (tr[2 * p + 1].add + tr[p].add) % mod;
		tr[2 * p].mul = (tr[2 * p].mul * tr[p].mul) % mod;
		tr[2 * p + 1].mul = (tr[2 * p + 1].mul * tr[p].mul) % mod;

		tr[2 * p].sum %= mod;
		tr[2 * p].mul %= mod;
		tr[2 * p + 1].sum %= mod;
		tr[2 * p + 1].mul %= mod;
		tr[p].add = 0;
		tr[p].mul = 1;
	}
}
void build(int p, int l, int r)
{
	tr[p] = { l,r,w[l],0,1 };
	if (l == r)return;
	int m = (l + r) / 2;
	build(2 * p, l, m);
	build(2 * p + 1, m + 1, r);
	pushup(p);
}
void update(int p, int x, int k)
{
	if (tr[p].l == x && tr[p].r == x)
	{
		tr[p].sum = (tr[p].sum + k) % mod;
		return;
	}
	int m = (tr[p].l + tr[p].r) / 2;
	if (x <= m)update(2 * p, x, k);
	else update(2 * p + 1, x, k);
	pushup(p);
}
void update(int p, int x, int y, int k)
{
	if (x <= tr[p].l && tr[p].r <= y)
	{
		tr[p].sum = (tr[p].sum + (tr[p].r - tr[p].l + 1) * k) % mod;
		tr[p].add = (tr[p].add + k) % mod;
		return;
	}
	int m = (tr[p].l + tr[p].r) / 2;
	pushdown(p);
	if (x <= m)update(2 * p, x, y, k);
	if (y >= m + 1)update(2 * p + 1, x, y, k);
	pushup(p);
}
void multiple(int p, int x, int y, int k)
{
	if (x <= tr[p].l && tr[p].r <= y)
	{
		tr[p].sum = (tr[p].sum * k) % mod;
		tr[p].add = (tr[p].add * k) % mod;
		tr[p].mul = (tr[p].mul * k) % mod;
		return;
	}
	int m = (tr[p].l + tr[p].r) / 2;
	pushdown(p);
	if (x <= m)multiple(2 * p, x, y, k);
	if (y >= m + 1)multiple(2 * p + 1, x, y, k);
	pushup(p);
}
int query(int p, int x, int y)
{
	if (x <= tr[p].l && tr[p].r <= y)
	{
		return tr[p].sum % mod;
	}
	int m = (tr[p].l + tr[p].r) / 2;
	pushdown(p);
	int sum = 0;
	if (x <= m)sum = (sum + query(2 * p, x, y)) % mod;
	if (y >= m + 1) sum = (sum + query(2 * p + 1, x, y)) % mod;
	return sum % mod;
}
signed main()
{
	ios::sync_with_stdio(0);
	int m;
	cin >> n >> m >> mod;
	for (int i = 1; i <= n; i++)cin >> w[i];
	build(1, 1, n);
	for (int i = 1; i <= m; i++)
	{
		int op;
		cin >> op;
		if (op == 1)
		{
			int x, y, k;
			cin >> x >> y >> k;
			multiple(1, x, y, k);
		}
		else if (op == 2)
		{
			int x, y, k;
			cin >> x >> y >> k;
			update(1, x, y, k);
		}
		else
		{
			int x, y;
			cin >> x >> y;
			cout << query(1, x, y) << endl;
		}
	}
	return 0;
}

标签：int,sum,tr,节点,add,mul,线段
From： https://www.cnblogs.com/susenyang/p/17636362.html

相关文章

  • 线段树进阶-分裂合并
    前置知识动态开点权值线段树相信各位都会线段树合并我们考虑对于两棵权值线段树，由于动态开点的缘故，这两棵树都是不满的我们考虑能不能把这两棵树所保存的信息合并在一起我们考虑这么一件事就是说，由于树不满，我们可以暴力扫分为三种情况(设把\(b\)所在树并到\(a\)内，\(a\)......
  • POJ 2828(线段树 单点更新)
    BuyTicketsTimeLimit: 4000MS MemoryLimit: 65536KTotalSubmissions: 16466 Accepted: 8201DescriptionRailwayticketsweredifficulttobuyaroundtheLunarNewYearinChina,sowemustgetupearlyandjoinalongqueue…TheLunarNewYearwasap......
  • ZOJ 3911 线段树（区间更新）
    PrimeQueryTimeLimit: 1Second     MemoryLimit: 196608KBYouaregivenasimpletask.Givenasequence A[i] with NHerearetheoperations:Avl,addthevalue v toelementwithindex l.(1<=V<=1000)Ralr,replacealltheelementsofse......
  • HDU 4893(线段树区间更新)
    Wow!SuchSequence!TimeLimit:10000/5000MS(Java/Others)    MemoryLimit:65536/65536K(Java/Others)TotalSubmission(s):3856    AcceptedSubmission(s):1085ProblemDescriptionRecently,Dogegotafunnybirthdaypresentfromhisnewf......
  • HDU 1698（线段树 区间更新）
    JustaHookTimeLimit:4000/2000MS(Java/Others)    MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):23481    AcceptedSubmission(s):11758ProblemDescriptionInthegameofDotA,Pudge’smeathookisactuallythemosthorr......
  • [蓝桥杯 2021 省 B] 双向排序 (线段树)
    调了整整5个小时,结果发现自己建树的方式有误,气死我了气死我了,比较好的一道线段树(虽然我不会-----#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+10;intn,m,res,point;vector<int>v[2];//用于存储结果的数组，下标0表示sum为0，下标1表示sum为1structno......
  • 线段相交Ⅲ
    描述 线段相交有两种情形：一种是“规范相交”，另一种是“非规范相交”。规范相交是指两条线段恰有唯一一个不是端点的公共点。即如果一条线段的端点在另一条线段上则不视为相交。如果两条线段有部分重合，也不视为相交。而非规范相交则把以上两种情况都视为相交。如下图所示：规范......
  • 「学习笔记」线段树优化建图
    在建图连边的过程中，我们时常会碰到这种题目，一个点向一段连续的区间中的点连边或者一个连续的区间向一个点连边，如果我们真的一条一条连过去，那一旦点的数量多了复杂度就爆炸了，这里就需要用线段树的区间性质来优化我们的建图了。那棵线段树大概长这个样子。到时候加边的时候是这个......
  • 线段树
    线段树线段树是一种二叉树形数据结构，用于解决区间查询和区间修改问题。它将一个数组划分为若干个连续的区间，每个区间对应线段树的一个节点。通过递归地构建线段树，我们可以在O(logn)的时间复杂度内完成区间查询和区间修改操作。原理线段树的构建过程如下：将原数组划分为n个子......
  • 在不完全重合的情况下，判断线经过另一线段的方法
    importlogginglogging.basicConfig(level=logging.INFO,format='%(asctime)s-%(filename)s[line:%(lineno)d]-%(levelname)s:%(message)s',datefmt='%Y-%m-%d%H:%M:%S')importnumpyasnpfromshapely.......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99