线段树标记顺序问题

标签:代码   有关   多重   数值   基础   怎么   运算符   维护   lock   

作者:sshwy

黄队稳了!

引言

首先,在具备基础的线段树知识后,我们以结构化的语言描述线段树维护序列区间变动信息的方式:

首先有若干种对序列区间的数据的操作\(\alpha_1,\ldots,\alpha_k\),以及若干种数据分析操作(求值)\(\beta_1,\ldots,\beta_l\)。在代码实现的过程中我们通常对每种操作使用一个标记\(a_1,\ldots,a_k\),对每种分析维护一个权值\(b_1,\ldots,b_l\)。这些标记和权值构成了线段树上一个结点的信息。

使用线段树维护的信息,需要满足 \(\beta_1,\ldots,\beta_l\) 都具有结合律或者前缀结合律。说白了,就是能够用左右儿子的信息来更新父节点信息。

对于操作,我们要求他们能快速求值。也就是说每个操作\(\alpha_i\)对应一个方法\(A_i(u,v)\),表示对结点\(u\)代表的区间施加\(\alpha_i\)操作,参数为\(v\)。该方法的复杂度应是\(O(k+l)\)的。通常来说,\(A_i(u,v)\)会对\(u\)的权值和标记都产生影响。它会把\(u\)的权值更新为,进行了\(\alpha_i\)参数为\(v\)的操作后的权值,并累加\(\alpha_i\)操作对应的标记。\(u\)结点的标记是指\(u\)子节点的尚未进行的操作。说白了,\(u\)的权值是准的,而\(u\)子节点的权值是不准的。

有标记,就有标记的下传。而这就关系到了下传的顺序的问题,也是本文要探讨的重点。

先加还是先乘

最经典的问题莫过于加乘标记下传问题:

支持区间加,区间乘,区间求和。

结论:先下传乘法标记,再下传加法标记。并且对于乘法操作对应的方法,它需要对加法标记做一定的影响。

换言之,对 \(u\)父节点 \(p\) 的两个标记\(p_{\text{add}},p_{\text{mul}}\),则\(u\)被更新的过程为

\[\begin{aligned} u_{\text{sum}} &\gets u_{\text{sum}}\times p_{\text{mul}} + p_{\text{add}}\times\ell(u)\u_{\text{add}} &\gets u_{\text{add}}\times p_{\text{mul}} + p_{\text{add}}\u_{\text{mul}} &\gets u_{\text{mul}}\times p_{\text{mul}} \end{aligned} \]

注:\(\ell(u)\)表示\(u\)对应区间的长度。

可以发现这个更新本质上是先乘上了\(p_{\text{mul}}\),再加上了\(p_{\text{add}}\)。并且\(p_{\text{mul}}\)影响了\(u_{\text{add}}\),也就是标记之间的影响。

那么为什么不能先加后乘?

举个例子。对 \(u\)父节点 \(p\) 的两个标记\(p_{\text{add}},p_{\text{mul}}\),如果我们按照先加后乘的顺序更新

\[u_{\text{sum}} \gets (u_{\text{sum}} + p_{\text{add}}\times\ell(u))\times p_{\text{mul}} \]

那么,我们考虑\(p_{\text{add}}\)怎么更新\(u_{\text{add}}\)

我们不能直接\(u_{\text{add}}\gets u_{\text{add}} + p_{\text{add}}\)。因为这就相当于是把 \((v+u_{\text{add}})\times u_{\text{mul}}\) 变成了 \((v+(u_{\text{add}}+p_{\text{add}})\ell(u))\times u_{\text{mul}}\),而我们想要的是\((v+u_{\text{add}}\ell(u))\times u_{\text{mul}} + p_{\text{add}}\ell(u)\)。这里的\(v\)代指\(u\)的儿子结点。

也就是说,我们必须把\(u_{\text{mul}}\)变成\(1\),才能\(u_{\text{add}}\gets u_{\text{add}} + p_{\text{add}}\)。把\(u_{\text{mul}}\)变成\(1\),就意味着将\(u\)的标记下传。因此问题出现了:要下传\(p\)的标记,我们就得下传\(u\)的标记。因此复杂度就不对了。

由此引出了一个问题:两个操作的先后顺序要通过怎样的性质来判断?

再探先乘后加

回到先乘后加的问题上。为方便后文表述,我们将更新前和更新后的权值做一个区分:

\[\begin{aligned} u_{\text{sum}}‘ &\gets u_{\text{sum}}\times p_{\text{mul}} + p_{\text{add}}\times\ell(u)\u_{\text{add}}‘ &\gets u_{\text{add}}\times p_{\text{mul}} + p_{\text{add}}\u_{\text{mul}}‘ &\gets u_{\text{mul}}\times p_{\text{mul}} \end{aligned} \]

判断这个更新是否合法,主要是比较,对于\(u\)的子节点\(v\),将\(v\)先用\(u_{\text{add}},u_{\text{mul}}\)更新,再用\(p_{\text{add}},p_{\text{mul}}\)更新:

\[( v\times u_{\text{mul}}+u_{\text{add}}\ell(v) )\times p_{\text{mul}}+p_{\text{add}}\ell(v) \]

\(v\)\(u‘_{\text{add}},u‘_{\text{mul}}\)更新:

\[v\times u_{\text{mul}}‘+u_{\text{add}}‘\ell(v) \]

看两者是否相等。显然,代入一下就可以发现,两者的确相等。

这样,我们就可以总结出一般化的线段树多重信息维护方式。

一般化

对于操作\(\alpha_1,\ldots,\alpha_k\),设它们对应的运算符分别为\(\bigcirc_1,\ldots,\bigcirc_k\)。对于分析\(\beta_1,\ldots,\beta_l\),设它们对应的运算符分别为\(\square_1,\ldots,\square_l\)。那么称由\(\bigcirc_i,\square_i\)和数值交替排列构成的算式为相关多项式

我们定义变量结点,表示结点的信息都是变量。

如果存在一种更新方式\(u\gets \text{upd}(u,p)\),使得对于变量结点\(v\)\(\text{upd}(\text{upd}(v,u),p)\)得到的相关多项式能与\(\text{upd}(v,u)\)的相关多项式的结构一一对应(也就是说变量的系数可以不同,但与变量有关的运算过程是对应的),那么这种更新方式就是满足复杂度要求的,可以应用于线段树。

应用 1

操作:区间加、区间乘、区间赋值

分析:区间和

顺序:先区间乘,再区间加,最后区间赋值。

则用\(u\)更新\(v\)

\[\text{cover}(v_{\text{sum}}\times u_m + u_a\ell(v),u_c) \]

先用\(u\)再用\(p\)更新\(v\)

\[\begin{aligned} & \text{cover}(\text{cover}(v_{\text{sum}}\times u_m + u_a\ell(v),u_c)\times p_m + p_a\ell(v),p_c)\= & \text{cover}(\text{cover}(v_{\text{sum}}\times u_m\times p_m + (u_a\times p_m + p_a)\ell(v),u_c),p_c) \end{aligned} \]

这样我们就得到了更新方程:

\[\begin{aligned} u_m&\gets u_m\times p_m\u_a&\gets u_a\times p_m + p_a\u_c&\gets \text{cover}(u_c,p_c) \end{aligned} \]

线段树标记顺序问题

标签:代码   有关   多重   数值   基础   怎么   运算符   维护   lock   

原文地址:https://www.cnblogs.com/dysyn1314/p/13938612.html

版权声明:完美者 发表于 2020-11-07 16:39:36。
转载请注明:线段树标记顺序问题 | 完美导航

暂无评论

暂无评论...