Skip to main content

线段树

参考资料​

实现​

773 Bcpp
struct SEG
{
	ll a[N],val[N<<2],tag[N<<2];
	void gx(int u,ll v,int len){val[u]+=v*len;tag[u]+=v;}
	void push_up(int u){val[u]=val[ls]+val[rs];}
	void push_down(int u,int l,int r)
	{
		gx(ls,tag[u],mid-l+1);
		gx(rs,tag[u],r-mid);
		tag[u]=0;
	}
	void build(int u,int l,int r)
	{
		if(l==r){val[u]=a[l];return;}
		build(ls,l,mid);
		build(rs,mid+1,r);
		push_up(u);
	}
	void update(int u,int l,int r,int x,int y,ll v)
	{
		if(x<=l&&r<=y){gx(u,v,r-l+1);return;}
		push_down(u,l,r);
		if(x<=mid)update(ls,l,mid,x,y,v);
		if(y>mid)update(rs,mid+1,r,x,y,v);
		push_up(u);
	}
	ll query(int u,int l,int r,int x,int y)
	{
		if(x<=l&&r<=y)return val[u];
		push_down(u,l,r);
		ll res=0;
		if(x<=mid)res+=query(ls,l,mid,x,y);
		if(y>mid)res+=query(rs,mid+1,r,x,y);
		return res;
	}
};

例题​

洛谷 P3372 【模板】线段树 1

如题，已知一个数列 {ai}\{a_i\}，你需要进行下面两种操作：

  1. 将某区间每一个数加上 kk。
  2. 求出某区间每一个数的和。
洛谷 P13825 【模板】线段树 1.5

如题，已知一个长度为 nn 的数列 {ai}\{a_i\}（1≤i≤n1 \leq i \leq n），初始时 aa 序列满足 ai=ia_i = i。你需要进行下面两种操作：

  1. 将某区间每一个数加上 kk。
  2. 求出某区间每一个数的和。
洛谷 P3373 【模板】线段树 2

如题，已知一个数列 aa，你需要进行下面三种操作：

  • 将某区间每一个数乘上 xx；
  • 将某区间每一个数加上 xx；
  • 求出某区间每一个数的和。
洛谷 P4588 [TJOI2018] 数学计算

小豆现在有一个数 xx，初始值为 11。小豆有 QQ 次操作，操作有两种类型：

1 m：将 xx 变为 x×mx \times m，并输出 x mod Mx \bmod M

2 pos：将 xx 变为 xx 除以第 pospos 次操作所乘的数（保证第 pospos 次操作一定为类型 1，对于每一个类型 1 的操作至多会被除一次），并输出 x mod Mx \bmod M。

洛谷 P1471 方差

第一行包含两个正整数 N,MN,M，分别表示数列中实数的个数和操作的个数。

第二行包含 NN 个实数，其中第 ii 个实数表示数列的第 ii 项。

接下来 MM 行，每行为一条操作，格式为以下三种之一：

操作 11：1 x y k，表示将第 xx 到第 yy 项每项加上 kk，kk 为一实数。 操作 22：2 x y，表示求出第 xx 到第 yy 项这一子数列的平均数。 操作 33：3 x y，表示求出第 xx 到第 yy 项这一子数列的方差。

洛谷 P4556 【模板】线段树合并 / [Vani 有约会] 雨天的尾巴

村落里一共有 nn 座房屋，并形成一个树状结构。然后救济粮分 mm 次发放，每次选择两个房屋 (x,y)(x, y)，然后对于 xx 到 yy 的路径上（含 xx 和 yy）每座房子里发放一袋 zz 类型的救济粮。

然后深绘里想知道，当所有的救济粮发放完毕后，每座房子里存放的最多的是哪种救济粮。

洛谷 CF786B Legacy

Rick 和他的同事们做出了一种新的放射性配方，与此同时很多坏人正追赶着他们。因此 Rick 想在坏人们捉到他之前把他的遗产留给 Morty。

在宇宙中一共有 nn 个星球标号为 1∼n1\sim n。Rick 现在身处于标号为 ss 的星球（地球）但是他不知道 Morty 在哪里。

众所周知，Rick 有一个传送枪，他用这把枪可以制造出一个从他所在的星球通往其他星球（也包括自己所在的星球）的单行道路。但是由于他还在用免费版，因此这把枪的使用是有限制的。

默认情况下他不能用这把枪开启任何传送门。在网络上有 qq 个售卖这些传送枪的使用方案。每一次你想要实施这个方案时你都可以购买它，但是每次购买后只能使用一次。每个方案的购买次数都是无限的。

网络上一共有三种方案可供购买：

  • 开启一扇从星球 vv 到星球 uu 的传送门；
  • 开启一扇从星球 vv 到标号在 [l,r][l,r] 区间范围内任何一个星球的传送门。（即这扇传送门可以从一个星球出发通往多个星球）；
  • 开启一扇从标号在 [l,r][l,r] 区间范围内任何一个星球到星球 vv 的传送门。（即这扇传送门可以从多个星球出发到达同一个星球）；

Rick 并不知道 Morty 在哪儿，但是 Unity 将要通知他 Morty 的具体位置，并且他想要赶快找到通往所有星球的道路各一条并立刻出发。因此对于每一个星球（包括地球本身）他想要知道从地球到那个星球所需的最小钱数。