线段树维护区间历史信息和为例的复杂信息维护同标记下传设计技巧简记

· · 算法·理论

思路

单次影响与维护信息

首先考虑每一种修改操作单次对信息的影响，特殊地，将统计历史信息也视作一次操作。比如，区间加，统计区间历史信息和两种操作可以表示成：

sum\gets sum+v\cdot len\\ ans\gets ans+sum

同时，我们可以知道要维护三个信息：len,sum,ans，分别表示区间长度、区间和、区间历史信息和。

设计标记与影响信息

然后我们想象，对当前区间的所有单次操作，按顺序排在一个队列里面，比如记区间加操作为 \mathrm A，统计区间历史信息和操作为 \mathrm S，可能有操作队列：

\mathrm {AAASAASASAAS}\dots

我们所设计的标记，其实就是提取出上面队列的关键信息以代表整个队列。

我们先考虑这整个队列中所有 \mathrm A 操作对 sum 的影响，有：

sum\gets sum+len\sum_{i\in Queue}[type_i=\mathrm A]v_i

因此我们需要维护的一个标记就是所有 \mathrm A 操作的权值之和。

然后考虑整个队列中所有 \mathrm S 操作对 ans 的影响，有：

ans\gets ans+\sum_{i\in Queue}[type_i=\mathrm S](sum+len\sum_{j<i}[type_j=\mathrm A]v_j)

拆开：

ans\gets ans+(\sum_{i\in Queue}[type_i=\mathrm S])\cdot sum+(\sum_{i\in Queue}[type_i=\mathrm S]\sum_{j<i}[type_j=\mathrm A]v_j)\cdot len

因此，我们需要维护两个标记，一个是队列中 \mathrm S 操作的数量，另一个是队列中所有 \mathrm S 操作的前缀 \mathrm A 操作权值和，也就是每一次 \mathrm S 操作当时的 \mathrm A 操作权值和之和。

整理一下：

我们需要维护三个标记，令作：

taga=\sum_{i\in Queue}[type_i=\mathrm A]v_i\\ cnts=\sum_{i\in Queue}[type_i=\mathrm S]\\ tags=\sum_{i\in Queue}[type_i=\mathrm S]\sum_{j<i}[type_j=\mathrm A]v_j

他们对信息的影响为（请注意，右式中的信息均为修改前的原值）：

sum\gets sum+len\cdot taga\\ ans\gets ans+cnts\cdot sum+len\cdot tags

队列拼接与标记下传

我们考虑标记下传的意义，实际上就是把父节点的操作序列，拼接在子节点的操作序列队尾。在后面，我们为新拼接的序列信息变量名后打上 ' 以示区分。

我们只需要根据想象中的拼接起来的队列模拟标记值的变化即可，这一步一般是简单的，比如上面的例子，有：

taga\gets taga+taga'\\ cnts\gets cnts+cnts'\\ tags\gets tags+sum\cdot cnts'+tags'

对 tags 的更新相对复杂些，中间项其实就是前半部分队列的和对后半部分队列统计的前缀和产生了影响。

到这里我们就已经完成了信息维护到标记下传的所有部分的设计。

例题

以 P8868 [NOIP2022] 比赛 为例。转化就不说了，简单来说，给出两个序列 a,b，我们要实现：

让我们通过上述方法开始设计。

首先，实际上有三种操作：区间加 a，区间加 b，统计历史信息。可以表示成：

S_a\gets S_a+len\cdot v,S_{ab}\gets S_{ab}+vS_b\\ S_b\gets S_b+len\cdot v,S_{ab}\gets S_{ab}+vS_a\\ ans\gets ans+S_{ab}

然后想象一个序列：

\mathrm{ABSABASAABBSBAS\dots}

为了方便，我们提前设计一下两个标记以防止后面的公式长的一批：

T_a=\sum_{i\in Queue}[type_i=\mathrm A]v_i\\ T_b=\sum_{i\in Queue}[type_i=\mathrm B]v_i

以及口述一下，记 S_{ab}(k) 表示进行到第 k 次操作时的 S_{ab} 信息，S_a(k) 表示进行到第 k 次操作时的 S_{a} 信息，S_b(k) 同理。

于是有：

S_a\gets S_a+len\cdot T_a\\ S_b\gets S_b+len\cdot T_b\\ S_{ab}\gets S_{ab}+S_b\cdot T_a+S_a\cdot T_b+len\cdot T_a\cdot T_b\\ ans\gets ans+\sum_{i\in Queue}[type_i=\mathrm S]S_{ab}(i)

我们考虑拆开 \sum_{i\in Queue}[type_i=\mathrm S]S_{ab}(i)。

ans\gets ans+\sum_{i\in Queue}[type_i=\mathrm S](S_{ab}+S_{a}(i)S_b+S_{b}(i)S_a+len\cdot S_a(i)S_b(i))

整理设计标记：

T_a=\sum_{i\in Queue}[type_i=\mathrm A]v_i\\ T_b=\sum_{i\in Queue}[type_i=\mathrm B]v_i\\ cnts=\sum_{i\in Queue}[type_i=\mathrm S]\\ h_{a}=\sum_{i\in Queue}[type_i=\mathrm S]S_a(i)\\ h_{b}=\sum_{i\in Queue}[type_i=\mathrm S]S_b(i)\\ h_{ab}=\sum_{i\in Queue}[type_i=\mathrm S]S_{ab}(i)\\

整理对四种信息的影响（同理，右式内变量为原值）：

S_a\gets S_a+len\cdot T_a\\ S_b\gets S_b+len\cdot T_b\\ S_{ab}\gets S_{ab}+S_b\cdot T_a+S_a\cdot T_b+len\cdot T_a\cdot T_b\\ ans\gets ans+S_{ab}cnts+h_aS_b+h_bS_a+len\cdot h_ah_b

然后我们考虑合并序列、下传标记，比较简单，直接给出结果，记号同上：

T_a\gets T_a+T_a'\\ T_b\gets T_b+T_b'\\ cnts\gets cnts+cnts'\\ h_a\gets h_a+T_a\cdot cnts'+h_a'\\ h_b\gets h_b+T_b\cdot cnts'+h_b'\\ h_{ab}\gets h_{ab}+T_aT_b\cdot cnts'+T_a\cdot h_b'+T_b\cdot h_a'+h_{ab}'

然后就做完啦。

给出我实现的信息结构体代码：

struct node{
    ull len=0,sa=0,sb=0,sab=0,ans=0,ta=0,tb=0,cq=0,ha=0,hb=0,hab=0;
    inline void operator*=(node t){
        ans+=sab*t.cq+t.ha*sb+t.hb*sa+t.hab*len;
        sab+=t.ta*sb+t.tb*sa+t.ta*t.tb*len;
        sa+=t.ta*len,sb+=t.tb*len;
        cq+=t.cq;
        hab+=ta*tb*t.cq+ta*t.hb+tb*t.ha+t.hab;
        ha+=ta*t.cq+t.ha,hb+=tb*t.cq+t.hb;
        ta+=t.ta,tb+=t.tb;
    }
    friend inline node operator+(node a,node b){
        node c;
        c.len=a.len+b.len;
        c.sa=a.sa+b.sa;
        c.sb=a.sb+b.sb;
        c.sab=a.sab+b.sab;
        c.ans=a.ans+b.ans;
        return c;
    }
}