浅谈线段树信息合并

基础线段树告诉我们，每个节点保存对应区间的摘要 Info，父节点再由左右儿子的摘要合并得到。

不过在真实问题中，难点在于到底留下什么信息，以及信息之间是如何合并的。在这个角度下，线段树的 merge 其实跟 二分答案的 check 很像。

对于区间和、最大值这类简单问题，答案本身就足够成为摘要。但当父区间中可能产生子区间内部没有出现过的新答案时，只保存当前答案就不再充分。

本文从具体问题出发，观察区间摘要怎样因为新的合并需求不断增加。最后再讨论，信息合并怎样从几个统计量推广到有限状态与状态转移。

一、答案本身什么时候已经足够

若父区间的答案能直接由两个子区间的答案合并，那么就不需要额外接口。

区间和取两侧之和，区间最大值取两侧最大值，颜色集合则取两侧集合的并即可。

P1558 色板游戏：集合本身就是摘要

Q1

P1558 色板游戏
一块长色板初始全部为第一种颜色，支持把一段区间覆盖成指定颜色，以及询问一段区间出现了多少种颜色。

数据规模：长度和操作数均不超过 $10^5$，颜色不超过 $30$ 种。

由于颜色种类很少，所以一个区间出现过的颜色可以直接压成一个二进制集合 mask，第 $c$ 位表示颜色 $c$ 是否出现。

左右区间合并时，只需要按位或即可得到父区间的颜色集合。最终查询得到完整 mask 后，再统计其中二进制位为 $1$ 的个数。

由于答案需要的完整信息在合并后没有丢失，当前区间的颜色集合本身既能回答询问，也能直接恢复父区间的同一种摘要，所以不需要额外状态。

当然本题还包含区间覆盖操作，相关内容在 浅谈线段树懒标记 中讨论。

二、统计量本身也可以设计成可合并状态

P1471 方差：补齐统计量的合并条件

Q2

P1471 方差
给定一个长度为 $N$ 的序列，支持区间加，并查询区间平均值与方差。

数据规模：$N,M\le 10^5$。

平均值比较容易处理，只要知道区间和与区间长度即可恢复。真正有意思的是方差应该怎样维护。

比较自然的想法是直接让节点保存方差本身，但是左右区间各自的方差无法直接合并得到整体方差，所以问题是 “方差” 单独不对区间拼接封闭，还需要补上区间长度、区间和与平均数。

设左右区间长度分别为 $x,y$，平均数分别为 $\mu_L,\mu_R$，方差分别为 $s_L,s_R$，合并后的平均数为 $\mu$。由方差定义，将左右两部分分别展开，可以得到：

$$\begin{aligned} s &=\frac{1}{x+y}\left(\sum_{i\in L}(A_i-\mu)^2+\sum_{i\in R}(A_i-\mu)^2\right)\\ &=\frac{x}{x+y}\left(s_L+(\mu_L-\mu)^2\right) +\frac{y}{x+y}\left(s_R+(\mu_R-\mu)^2\right), \end{aligned}$$

其中 $\displaystyle \mu=\frac{x\mu_L+y\mu_R}{x+y}$，所以可以直接把平均数与方差放进 Info，并用同一套公式稳定合并：

▶

方差统计量的合并

struct Info {
    int len;
    double sum, avg, var;
    // average | variance
};

Info merge( const Info &L, const Info &R ) {
    if( L.len == 0 ) return R;
    if( R.len == 0 ) return L;
    Info res = { L.len + R.len, L.sum + R.sum };
    res.avg = res.sum / res.len;
    int x = L.len, y = R.len;
    res.var = 1.0 * x / ( x + y )
          * ( L.var + ( L.avg - res.avg ) * ( L.avg - res.avg ) )
          + 1.0 * y / ( x + y )
          * ( R.var + ( R.avg - res.avg ) * ( R.avg - res.avg ) );
    return res;
}

Info make_info( double x ) {
    return { 1, x, x, 0 };
}

/* 中间略 */

Info ask( int u, int l, int r ) {
    if( l <= tr[u].l && tr[u].r <= r ) return tr[u].info;
    push_down( u );
    int mid = ( tr[u].l + tr[u].r ) >> 1;
    if( mid < l ) return ask( rs, l, r );
    if( r <= mid ) return ask( ls, l, r );
    return merge( ask( ls, l, r ), ask( rs, l, r ) );
}

当然，本题也可以改为维护一次和与平方和，再由查询结果恢复方差。区间加如何作用于这些摘要，则放在 浅谈线段树懒标记 中讨论。

三、边界信息

P4513 小白逛公园：跨过分界线的新答案

Q3

P4513 小白逛公园
给定一个可能含负数的序列，支持单点修改。每次查询一个区间内非空连续子段的最大和。

数据规模为 $n\le 5\times 10^5$、$m\le 10^5$。

既然只有单点修改和区间查询，可以直接使用 线段树基础理论 的基础结构。最自然的想法，是让每个节点只保存当前区间的最大子段和 mx。

考虑父区间由左右两个子区间拼成。父区间的最大子段可能完全来自左儿子，完全来自右儿子，也可能是跨越中点的。

前两种情况可以分别从 L.mx 与 R.mx 得到，但第三种情况没法在只知道两侧最大子段的情况下推出来，问题在于当前没有保留跨边界合并所需的信息。

本题中，跨中点的连续子段一定由左区间的某个后缀和右区间的某个前缀组成，因此还需要分别保存最大后缀 rmx 和最大前缀 lmx。

当然，由于父区间的最大前缀可能完全位于左区间，也可能覆盖整个左区间后继续进入右区间。为了计算后一种情况，还要知道左区间总和 sum，最大后缀的推导同理。

所以我们发现，本题一共需要维护四项信息，而这些信息都是在查询中逐渐被 “逼” 出来的：

• sum：整个区间的总和 | mx：最大非空子段和。
• lmx：最大非空前缀和 | rmx：最大非空后缀和。

▶

P4513 的区间摘要

struct Info {
    ll sum, mx;
    ll lmx, rmx;
};

struct Node {
    int l, r;
    Info info;
} tr[maxn << 2];

Info merge( const Info &L, const Info &R ) {
    Info res;
    res.sum = L.sum + R.sum;
    res.lmx = max( L.lmx, L.sum + R.lmx );
    res.rmx = max( R.rmx, R.sum + L.rmx );
    res.mx = max({ L.mx, R.mx, L.rmx + R.lmx });
    return res;
}

Info make_info( ll x ) {
    return { x, x, x, x };
}

笔记

叶子表示非空区间，所以四项和值都应初始化为元素本身。若把最优值与 $0$ 取最大值，全负的区间就会错误地选择题目不允许的空子段。

P6492 STEP：只有长度还不够

Q4

P6492 STEP
一个初始全为 L 的字符串会不断翻转单个位置。每次修改后，需要输出整个字符串中最长的、相邻字符均不相同的连续子串长度。

数据规模： $n,q\le 2\times 10^5$。

同上，本题也存在跨越中点的答案，所以还需要保存区间最长答案 mx，最长合法前缀 lmx，最长合法后缀 rmx。

同时注意左后缀不一定能跟右前缀连接，所以还需要存两个端点的值 lv 和 rv。

即使边界可以连接，父区间的最长前缀也不一定会进入右侧。只有左区间的合法前缀已经覆盖整个左区间，即 L.lmx == L.len 时，它才可能继续接上右区间的合法前缀。

最大后缀完全对称，需要先判断 R.rmx == R.len。父区间内部答案则先继承两侧答案，边界可以连接时再考虑 L.rmx + R.lmx。

▶

P6492 的边界接口

struct Info {
    int len, mx;
    int lmx, rmx;
    int lv, rv;
};

Info merge( const Info &L, const Info &R ) {
    Info res = { L.len + R.len, max( L.mx, R.mx ), L.lmx, R.rmx, L.lv, R.rv };
    if( L.rv != R.lv ) {
        res.mx = max( res.mx, L.rmx + R.lmx );
        if( L.lmx == L.len ) res.lmx = L.len + R.lmx;
        if( R.rmx == R.len ) res.rmx = R.len + L.rmx;
    }
    return res;
}

Info make_info( int x ) {
    return { 1, 1, 1, 1, x, x };
}

P7809 01 序列：不同结尾对未来并不等价

Q5

P7809 01 序列
给定一个静态 01 序列，需要多次查询区间最长不下降子序列或最长严格上升子序列。

数据规模：序列长度不超过 $10^6$，询问数不超过 $5\times 10^6$。

普通值域上的 LIS 需要用 DP 来转移状态。但 0/1 序列上的合法形态是有限的，即严格上升子序列只能是单个元素或 $0,1$，不下降子序列则一定具有若干个 $0$ 后接若干个 $1$ 的形态。

于是一个区间可以保存答案 lis 和 lnds 信息，同时为了合并，还需要额外存储 cnt0 和 cnt1。

然后再考虑区间之间的合并，lis 要么完全位于一侧，要么从左侧选择一个 $0$、从右侧选择一个 $1$。所以除了继承 L.lis 与 R.lis，只需检查 L.cnt0 > 0 且 R.cnt1 > 0 时能否得到长度 $2$。

lnds 可以理解为在某处分开已选的 $0$ 与 $1$。若分界发生在左区间，就取左侧最优 lnds，再接上右侧全部的 $1$；若分界发生在右区间，就取左侧全部的 $0$，再接上右侧最优 lnds。

因此父区间满足 lnds = max( L.lnds + R.cnt1, L.cnt0 + R.lnds )。

▶

P7809 的有限状态

struct Info {
    int cnt0, cnt1;
    int lis, lnds;
};

Info merge( const Info &L, const Info &R ) {
    Info res = { L.cnt0 + R.cnt0, L.cnt1 + R.cnt1 };
    res.lnds = max( L.lnds + R.cnt1, L.cnt0 + R.lnds );
    res.lis = max( L.lis, R.lis );
    if( L.cnt0 > 0 && R.cnt1 > 0 ) res.lis = max( res.lis, 2 );
    return res;
}

笔记

本题的更优实现可以预处理后使用 ST 表查询，但线段树写法仍然很适合观察有限状态怎样参与区间合并。

P5522 棠梨煎雪：摘要可以保存约束集合

Q6

P5522 [yLOI2019] 棠梨煎雪
有若干长度相同的 01 模式串，其中问号可以任选为零或一。支持修改一个模式串，并询问某个连续区间内所有模式串能够共同匹配多少个确定 01 串，最终输出所有询问答案的异或和。

数据规模：模式长度 $n\le 30$，模式串数量约为 $10^5$，操作数约为 $10^6$。

由于模式串很小，所以会想到可以状态压缩的思想。但是每个位置有三种可能性，特别是这个 ? 很难处理。

首先考虑没有 ? 的情况，只要某一个字符串的某一位是 1，那么其他串的这一位也必须是 1，否则就是不匹配的，当然 0 的情况也同理。

接着考虑合并区间，分别把各字符串中为 $1$ 和为 $0$ 的位置按位或，得到两份掩码 $S_1$ 与 $S_0$。若 $S_1\mathbin{\&}S_0$ 不为 $0$，就说明某个位置同时被要求为 1 和 0，区间内不存在共同匹配串。

如果没有修改，区间按位或可以用 ST 表在 $\mathcal{O}(1)$ 时间查询。不过本题需要动态修改，所以这里使用线段树维护这两份集合。

接着推广到有 ? 的情况。我们真正需要记录的是每一位是否被强制为 $0$ 或 $1$，而 ? 不产生任何强制条件，所以不需要单独保存第三种状态。

线段树上维护两个信息，分别表示每一位是否强制为 $1$，每一位是否强制为 $0$，然后区间合并沿用上面的分析即可。

注：区间合并时，两份必须集合分别按位或；若它们有交集，就出现同一位既要 0 又要 1 的冲突。

没有冲突时，未被两份集合覆盖的位置可以自由选择，若最后固定了 $k$ 位，方案数就是 $2^{n-k}$。

摘要

由此，发现 Info 保存的其实是这段区间对于未来合并时所需的最小有限状态。而只要状态规模足够小，而且两个状态能高效合并，就可以放在线段树节点中。

四、区间还可以表示一段有方向的行为

ABC467F：合并顺序本身就是摘要语义

ABC467F Email Scheduling Optimization 按等待回复时间从大到小安排邮件后，需要动态维护这一顺序下的完成时间。一个区间保存总编写时间 sum，以及从时间 $0$ 开始处理这段邮件时的最晚回复时间 mx。

若左区间必须先于右区间处理，右区间中的所有完成时间都会整体推迟 L.sum。于是父区间满足 sum = L.sum + R.sum，而 mx = max( L.mx, L.sum + R.mx )。

这里没有传统的最长前缀与最长后缀，但合并依然有明显方向。交换左右区间会改变处理顺序，也就可能改变最晚回复时间。

ABC456F：从保存状态到保存转移

ABC456F Plan Holidays 中，一个位置的作用可以写成对两维 DP 状态的一次 min-plus 转移。连续经过一段区间，就是按顺序执行这一段中的所有转移。

此时一个区间最自然的摘要不再是某个具体 DP 值，而是这一整段怎样把输入状态变成输出状态。若单个位置的转移写成矩阵，区间摘要就是这段矩阵的有序复合。

矩阵的合并顺序必须与状态向量的约定一致。若采用列向量且单点满足 next = M * prev，那么先经过左区间再经过右区间时，父转移应写成右转移乘左转移；换用行向量后顺序会相反，但两种实现都不能随意交换。

这已经没有传统意义上的“区间统计量”，却仍然符合线段树信息合并的共同结构。单个节点保存区间行为，左右行为可以复合，复合后仍然得到同一种行为。

五、合并与结合律

线段树对同一段序列采取固定的树形划分，而区间查询又会把若干节点按照不同的括号方式组合。为了让结果只由区间内容决定，而与括号分组无关，merge 必须满足结合律。

结合律不等于交换律，最大前缀与最大后缀、邮件处理顺序和矩阵转移等都具有方向，所以查询时必须保持原区间的左右顺序。

证明结合律时，不一定要把两种括号方式的公式全部展开。只要先证明 merge(L,R) 恰好恢复相邻区间拼接后的真实摘要，那么两种分组最终描述的都是同一个完整区间。

查询实现还要考虑空摘要。如果摘要存在单位元，就可以让空结果直接参与合并；若没有自然单位元，则应分别处理只进入左侧、只进入右侧和同时进入两侧的情况。

六、从询问反推 Info

遇到信息合并相关的问题时，可以依次检查下面六条事项。

1. 先确定完整的区间需要回答什么。
2. 枚举父区间答案是如何从左右儿子区间得到的。
3. 然后记录跨边界情况，左右儿子必须额外提供的信息。
4. 继续推导新增信息在父区间如何恢复，确认合并后仍保持相同语义。
5. 检查结合律、左右顺序与空摘要，并计算一次合并的真实代价。
6. 再检查题目的静态性、操作范围与数据规模，判断是否存在更轻的结构。

七、复杂度与适用边界

设一次合并的代价为 $T_{merge}$，那么建树复杂度为 $O(nT_{merge})$，单点修改与区间查询复杂度为 $O(T_{merge}\log n)$。普通常数维摘要的合并为 $O(1)$，矩阵或小型 DP 则要计入状态规模带来的额外代价。

理论上能够定义摘要，不表示它值得放进线段树。若摘要大小随区间长度增长，或者一次合并已经接近线性扫描，那么外层的对数结构也无法得到理想复杂度。

八、信息合并 & 区间操作

信息合并只研究一个区间最后留下什么，若是题目还有区间修改，还要继续判断一次操作能否直接更新这些摘要，以及多个待执行操作之间的先后次序。

线段树信息合并，更像是一种从父区间需求反推子区间信息的状态设计过程：先找出当前答案在合并时缺失了什么，再补充与相邻区间连接所需的接口。

如果接口具有多种可能，就把它扩展成有限状态。如果整个区间本身表示一段状态变化，也可以直接保存这段转移。