前言

这篇博客中的题有很多技巧，多看看...
玄学势能线段树（刚刚终于解决了，膜拜同机房 czx 大佬解释）

简单介绍势能线段树

其本质上是一种区间暴力修改技术。

考虑普通的区修线段树，我们使用 lazytag 来记录区间修改信息，在访问到当前节点之后再将当前节点的 tag 下传。

然而，有很多信息是不好下传的（不满足交换或结合律），于是我们就无法使用 tag 来记录区修信息。但有的题目每一个操作都有潜在的操作次数上限，我们可以先判断该区间有没有需要操作的节点，有的话遍历到叶子节点进行修改，没有的话返回。

普遍题目性质

一般需要不断取模（mod），开方（sqrt）或平方（^k）等增长或减小速度迅速的，且信息不易下传...

势能线段树的普遍时间复杂度分析

前置知识

有基础的势能线段树知识。

分析

首先引出一个普遍公式：

设 $n$ 为节点个数， $m$ 为查询数量， $O (m \times ∣ 0 势能时线段树操作时间复杂度 ∣ + n \times ∣ 节点势能上限降低至 0 势能时间复杂度 ∣ + m \times ∣ 线段树单次操作影响到的节点数目 ∣ \times ∣ 操作额外提供的势能 ∣)$

这个怎么说呢，前两个挺好理解的，一个是线段树的时间复杂度，一个是在操作时势能减小的时间复杂度；

这里重点讲讲最后一个，最后一个出现的情况前提是存在除了势能操作外的操作，比较抽象是吧，举个栗子：

假设我们现在有三个操作，个数为 $n$ ：

1.使区间 $[l, r]$ 内的所有数开平方；（我称其为势能操作，因为这个操作中每个数最多的操作次数与势能大小有关）

2.单点修改（升级版是区间修改） $x$ 位置上的数值；（即除了势能操作外的操作）

3.求区间 $[l, r]$ 的和。

很明显开平方不好用懒标记下传，考虑用势能线段树解决，若舍去操作 $2$ ，就是一个很板的势能线段树；

但加入操作 $2$ 时，可以考虑到每次势能变为 $0$ 时，都会被操作 $2$ 给重置，其实其时间复杂度并不会爆，为什么呢，因为是单点修改，最多修改 $m$ 次，每个数的最大势能依旧是 $\sqrt{V}$ ，这个势能也就是操作额外提供的势能；

那么我们再来想想线段树单次操作影响到的节点数目最大是多少呢？

因为是单点修改，所以对于每一个修改重置后的数，再次进行操作 $1$ 时，只可能会遍历树的最大深度，也就是说单次操作影响到的节点数目是 $l o g n$ 。

所以这个栗子的时间复杂度分析为 $O (m \times l o g n + n \times \sqrt{V} + m \times l o g n \times \sqrt{V})$ ，这边就不化简了...

问题又来了，若在升级版的区间修改中，每个修改区间为 $[1, n]$ 会不会使这个数目最大为 $n$ 呢？

升级版的操作 $2$ ：

2.把区间 $[l, r]$ 位置上的数值变为 $x$ （即平推区间）；（即除了势能操作外的操作）

下面划重点！！！

这里会讲的复杂点，耐心并感性理解一下：

同样，我们假设一开始全都是操作 $1$ ，使得全部位置上的势能都变为 $0$ ；

然后加入操作 $2$ ，把一个区间内的所有数平推，这里就需要一个优化了：

仔细想想，我们在前面处理操作 $1$ 都要遍历到叶子节点，原因是区间内不好进行懒标记下传，但是这时候的区间平推了，对于一个大区间，其实是可以像普通线段树那样懒标记区间开平方了（多想一下），那单次操作影响的节点数目不又变成了普通线段树的 $l o g n$ 了嘛！！！！

终于写完了此部分，累死了qwq。

会把比较有意义的题放在前面...

势能线段树的硬版本

[ABC256Ex] I like Query Problem

Solution

这个就是升级版的势能线段树，和普遍的势能线段树有不同之处，优化操作上面写了，这里不多讲了；

需要注意些代码细节（需要自己仔细思考一下）：

在操作 $1$ 时：

cpp

inline void update1(int rt,int l,int r,int s,int t,int k) {
	if(l>t||r<s)
		return ;
	if(!tree[rt].maxx)
		return ;
    */重点细节部分如下
	if(s<=l&&r<=t) {
		if(tree[rt].maxx==tree[rt].minx) {
			tree[rt].add=tree[rt].maxx/k;
			tree[rt].minx=tree[rt].minx/k;
			tree[rt].maxx=tree[rt].maxx/k;
			tree[rt].sum=(r-l+1)*tree[rt].add;
			return ;
		}
	}
    */重点细节部分如上
	push_down(rt,l,r);
	int mid=(l+r)>>1;
	update1(lson,l,mid,s,t,k);
	update1(rson,mid+1,r,s,t,k);
	push_up(rt);
	return ;
}

一些例题

数据结构平方

GSS4 - Can you answer these queries IV 模数

P4145 上帝造题的七分钟 2 / 花神游历各国开平方

SUM and REPLACE 约数

前言 ​

简单介绍势能线段树 ​

普遍题目性质 ​

势能线段树的普遍时间复杂度分析 ​

前置知识 ​

分析 ​

势能线段树的硬版本 ​

[ABC256Ex] I like Query Problem ​

Solution ​

一些例题 ​

前言