势能线段树浅析(Analysis of potential energy line segment tree)

势能线段树其实就是对于一些数据结构题,我们察觉到其中存在一些规律:

一段区间或某个点的修改次数不会超过 \(k\) 次, \(k\) 的值很小或为一个常数。

这样我们就可以在这个点修改了 \(k\) 次之后让它不再修改。

详解可见 link 。

这里我们转载一下其中最重要的几句话:

我们知道,线段树能够通过打标记实现区间修改的条件有两个:

  • 能够快速处理标记对区间询问结果的影响 。
  • 能够快速实现标记的合并 。
    但有的区间修改不满足上面两个条件(如区间开方,区间取模等)。

但某些修改存在一些奇妙的性质,使得序列每个元素被修改的次数有一个上限。

可以在线段树每个节点上记录一个值,表示对应区间内是否每个元素都达到修改次数上限。

区间修改时暴力递归到叶子节点,如果途中遇到一个节点,这个节点的对应区间内每个元素都达到修改次数上限则在这个节点 \(return\) 掉 。

可以证明复杂度为 \(O ( nlogn×\) 修改次数上限\()\) 。

推荐题目:

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

CF438D The Child and Sequence

CF920F SUM and REPLACE

————————

The potential energy line segment tree is actually for some data structure problems, we notice that there are some laws:

The modification times of an interval or a point will not exceed \ (K \) times, and the value of \ (K \) is very small or a constant.

In this way, we can modify this point \ (K \) times so that it will not be modified.

See link for detailed explanation.

Here we reprint some of the most important sentences:

We know that there are two conditions for segment trees to be able to modify intervals by marking:

  • It can quickly deal with the impact of markers on interval query results.
  • It can quickly merge tags.
    However, some interval modifications do not meet the above two conditions (such as interval square, interval modulus, etc.).

However, some modifications have some wonderful properties, so that there is an upper limit on the number of times each element of the sequence is modified.

A value can be recorded on each node of the segment tree to indicate whether each element in the corresponding interval has reached the upper limit of modification times.

When modifying an interval, it recurses to the leaf node. If a node is encountered on the way and each element in the corresponding interval of this node reaches the upper limit of modification times, it will be lost at this node \ (return \).

It can be proved that the complexity is \ (O (nlogn ×\) Maximum number of modifications \ () \).

Recommended topic:

P4145 seven minutes of God made questions 2 / Flower God travels around the world

CF438D The Child and Sequence

CF920F SUM and REPLACE