父节点向两个孩子索要什么

凌晨四点，旧法院还在审一桩没有被告的案子。

案卷里有五十万句口供。每句口供都有可信分，热心的证人给正分，喝多的证人给负分，门口保安的那句“我什么都没看见”单独占了 -7 分。

法官要找一段连续的证词，让陪审团听完以后最愿意点头。

书记员把案卷分成两摞，各自带走一半。约定很简单：只交摘要，不交原稿。

左边书记员回来，递上一张纸。

“我这摞最可信的一段，得分 12。”

右边书记员也递一张。

“我这摞是 9。”

法官把两摞纸合上。交接线恰好落在一段证词中间。

最可信的部分可能从左摞最后几句开始，穿过交接线，再接右摞开头的几句。

两张纸上的 12 和 9 安静得像两个无辜的人。它们拒绝告诉法官，自己的那段证词靠不靠边。

书记员补交第二版摘要：最好的开头，最好的结尾，整摞的总分。法官试着拼了一次，跨过交接线的证词终于有了分数。

案子还没结束。法官要求把两摞再各自拆成更小的摞，交给下一层书记员。

新摘要必须和旧摘要长得一样，才能继续往上交。

这条规矩写在案卷最后一页。没有人愿意读。

直到一个全是负分的案卷送进来。

书记员顺手把“没有证词”记成 0。法官听完空白，判出了比 -5 更高的可信度。

法庭里第一次有人认真读完了最后一页。

简化题面

┌─ [P4513] 小白逛公园
├─ 平台: 洛谷
├─ 题意: 维护一个整数序列，支持单点修改和区间最大非空子段和查询。
├─ 输入: 初始序列及若干修改、查询操作。
├─ 输出: 每次查询区间内的最大非空连续子段和。
├─ 数据范围: n <= 5e5，操作次数较大，需要对数级单次操作。
├─ 关键限制: 最优子段可能跨过左右区间的分界点。
└─ 完整题面: https://www.luogu.com.cn/problem/P4513

摘要为什么要有四格

区间被切成左右两部分。父区间的最佳连续段有三条路：全在左边，全在右边，跨过中点。

跨界那条路，左边只能取到右端，右边只能从左端开始。一个节点至少要交出：总和、最佳前缀、最佳后缀、最佳子段。

Node merge(Node L, Node R) {
    Node T;
    T.sum  = L.sum + R.sum;
    T.lmax = max(L.lmax, L.sum + R.lmax);
    T.rmax = max(R.rmax, R.sum + L.rmax);
    T.mx   = max({L.mx, R.mx, L.rmax + R.lmax});
    return T;
}

四格各有来路。

问总分，读取 sum。

问最佳开头，左边整摞接上右边的开头，要用 L.sum 和 R.lmax。

问最佳结尾，对称地要用 R.sum 和 L.rmax。

问最佳连续段，左、右、跨界三种候选都要保留。

合并完成后，摘要仍然是同一种摘要。更高一层可以继续读取。

这个性质叫闭合。

merge 也是查询过程里的 pushup。建树回溯时把结果写回 tree[p]。

查询跨过中点时，把左右返回值合成临时摘要。两处输入相同，公式可以共用。

空白证词不能抢走最高分

题目要求非空子段。单元素 [-5] 的答案就是 -5。

叶子四项全部初始化为自身。当前实现只递归有交集的孩子，避免构造一个全是 0 的假摘要。

if (qr <= mid) return query(p * 2, l, mid, ql, qr);
if (ql > mid) return query(p * 2 + 1, mid + 1, r, ql, qr);
return merge(query(p * 2, l, mid, ql, qr),
             query(p * 2 + 1, mid + 1, r, ql, qr));

样例输出是 2 和 -1。全负边界也通过了。

接下来可以用线性 Kadane 当另一位书记员，做随机对拍。一个负责维护摘要，一个负责把原稿从头听到尾。

法官把四格摘要盖回案卷。下一层书记员接过去，格式完全相同。

那桩没有被告的案子拖到天亮。最后一页只剩一句话：能继续交接的报告，才配叫报告。

发布信息草案

• 标题：父节点向两个孩子索要什么
• 摘要：最大子段和的节点字段来自跨分界线时仍会读取的信息，摘要还必须在合并后保持同型。
• 标签：线段树、最大子段和、pushup、merge、区间摘要