区间最大子段和的一点想法

· · 算法·理论

省流：线段树的三个标记最大子段和做法，但是不知道有什么用。

在思考一道题的时候同学给了个思路，发现可以放到最大子段和上。写文记录之。

传统的最大子段和做法需要维护四个变量，分别表示当前区间的 前缀最大值，后缀最大值，区间和，以及最大子段和。

传统做法的优点是容易支持修改，而且使用时间久、流传广、研究透彻。

我这个做法不知道有没有人提出来过，但是我在洛谷 GSS 系列的所有题解中都没有看到这个做法。

考虑原序列的前缀和，那么转化为 \max\limits_{L\le l\le r\le R}\{sum[r]-sum[l-1]\}。

特判掉区间不允许为空时的全负或者进行一些处理可以转化为 \max\limits_{L-1\le l\le r\le R}\{sum[r]-sum[l]\}。

这个东西是个比较经典的维护问题吧，直接维护区间最大值，区间最小值，以及答案。

inline friend Node operator+(const Node&x,const Node&y) {
    Node ans;ans.maxx=max(x.maxx,y.maxx);ans.minn=min(x.minn,y.minn);
    ans.ans=max({x.ans,y.ans,y.maxx-x.minn});return ans;
}

给一个我写的实现，以及AC记录。

我将这份代码删去不必要的内容之后扔给 deepseek，它告诉我这份代码的作用是"返回指定区间内的最大差值"。很显然，它说对了也没完全对。

这种做法的优点是可以拓展到一些其他方向（？，以及这种问题的另一种维护思路，以及在没有修改的时候常数略微小一点。缺点是原序列的单点修改都被转成了区间修改，有修改的时候常数可能会比较大。至于这种做法原序列能不能支持区间修改，我不知道。可能借助势能分析也能通过某种方式维护出来？但我不会。

这种做法做 GSS 5 好像也是三个标记，但是我还没有写。 upd:写了，过了。

如果有人找到了这种做法的出处，或者有相关博客，亦或者对这种做法感兴趣，欢迎私聊我。

不知道有什么用。

upd:发现可以做一个问题。

首先上树，然后我们考虑做一个节点相邻的所有节点加的操作。对于一个操作 (u,k)，如果 u 和 v 之间有连边那么将 v 的权值加 k。

传统做法没想到比较好的维护。毛毛虫剖分套第六分块。

考虑这个前缀和的思路，做一个树上前缀和，每个节点的前缀和为父节点的前缀和再加上自身权值。

这个操作对树上前缀和的影响是：父亲节点产生的影响，自己整个子树扣掉自己。维护一个加法标记就可以了。

给个实现云剪贴板。

跟暴力拍上了，应该没假。