作者：sshwy
黄队稳了！
引言
首先，在具备基础的线段树知识后，我们以结构化的语言描述线段树维护序列区间变动信息的方式：
首先有若干种对序列区间的数据的操作(alpha_1,ldots,alpha_k)，以及若干种数据分析操作（求值）(eta_1,ldots,eta_l)。在代码实现的过程中我们通常对每种操作使用一个标记(a_1,ldots,a_k)，对每种分析维护一个权值(b_1,ldots,b_l)。这些标记和权值构成了线段树上一个结点的信息。
使用线段树维护的信息，需要满足 (eta_1,ldots,eta_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_{ ext{add}},p_{ ext{mul}})，则(u)被更新的过程为
注：(ell(u))表示(u)对应区间的长度。
可以发现这个更新本质上是先乘上了(p_{ ext{mul}})，再加上了(p_{ ext{add}})。并且(p_{ ext{mul}})影响了(u_{ ext{add}})，也就是标记之间的影响。
那么为什么不能先加后乘？
举个例子。对 (u) 的父节点 (p) 的两个标记(p_{ ext{add}},p_{ ext{mul}})，如果我们按照先加后乘的顺序更新
那么，我们考虑(p_{ ext{add}})怎么更新(u_{ ext{add}})。
我们不能直接(u_{ ext{add}}gets u_{ ext{add}} + p_{ ext{add}})。因为这就相当于是把 ((v+u_{ ext{add}}) imes u_{ ext{mul}}) 变成了 ((v+(u_{ ext{add}}+p_{ ext{add}})ell(u)) imes u_{ ext{mul}})，而我们想要的是((v+u_{ ext{add}}ell(u)) imes u_{ ext{mul}} + p_{ ext{add}}ell(u))。这里的(v)代指(u)的儿子结点。
也就是说，我们必须把(u_{ ext{mul}})变成(1)，才能(u_{ ext{add}}gets u_{ ext{add}} + p_{ ext{add}})。把(u_{ ext{mul}})变成(1)，就意味着将(u)的标记下传。因此问题出现了：要下传(p)的标记，我们就得下传(u)的标记。因此复杂度就不对了。
由此引出了一个问题：两个操作的先后顺序要通过怎样的性质来判断？
再探先乘后加
回到先乘后加的问题上。为方便后文表述，我们将更新前和更新后的权值做一个区分：
判断这个更新是否合法，主要是比较，对于(u)的子节点(v)，将(v)先用(u_{ ext{add}},u_{ ext{mul}})更新，再用(p_{ ext{add}},p_{ ext{mul}})更新：
将(v)用(u'_{ ext{add}},u'_{ ext{mul}})更新：
看两者是否相等。显然，代入一下就可以发现，两者的确相等。
这样，我们就可以总结出一般化的线段树多重信息维护方式。
一般化
对于操作(alpha_1,ldots,alpha_k)，设它们对应的运算符分别为(igcirc_1,ldots,igcirc_k)。对于分析(eta_1,ldots,eta_l)，设它们对应的运算符分别为(square_1,ldots,square_l)。那么称由(igcirc_i,square_i)和数值交替排列构成的算式为相关多项式。
我们定义变量结点，表示结点的信息都是变量。
如果存在一种更新方式(ugets ext{upd}(u,p))，使得对于变量结点(v)，( ext{upd}( ext{upd}(v,u),p))得到的相关多项式能与( ext{upd}(v,u))的相关多项式的结构一一对应（也就是说变量的系数可以不同，但与变量有关的运算过程是对应的），那么这种更新方式就是满足复杂度要求的，可以应用于线段树。
应用 1
操作：区间加、区间乘、区间赋值
分析：区间和
顺序：先区间乘，再区间加，最后区间赋值。
则用(u)更新(v)：
先用(u)再用(p)更新(v)：
这样我们就得到了更新方程：