算法思维

增量维护：一种统一的算法思想

增量维护的核心哲学只有一句话：与其每次从头重新计算，不如在上一次结果的基础上，只处理"变化的部分"。 变化的部分通常很小，因此摊还代价远低于重新计算。下面按照维护目标分类展开。

一、维护窗口内的极值：单调队列

这就是你刚刚学的。场景特征是：有一个滑动窗口在数组上移动，每次需要知道窗口内的最大值或最小值。

单调队列的增量方式是：窗口右边新增一个元素时，从队尾淘汰所有"永远不可能成为答案"的旧元素；窗口左边有元素过期时，从队头弹出。队头始终是当前窗口的极值，O(1) 读取。每个元素一生只入队、出队各一次，总代价 O(n)。

如果没有窗口长度限制，只需要维护极值本身，一个变量就够了。单调队列处理的是"有范围约束的极值维护"这个更难的版本。

二、维护历史前缀信息：前缀和与前缀积

前缀和数组 P 本身就是一种增量维护。P[i+1] = P[i] + nums[i]，每一步只在上一步结果上加一个数，而不是重新对 [0..i] 求和。它把"任意区间求和"从 O(n) 降到 O(1) 查询。

前缀积、前缀异或、前缀最大值，都是同一个思想在不同运算下的推广。关键在于这个运算必须满足"可拆分性"：f(i,j) = g(f(0,j), f(0,i-1))，即区间答案可以由两个前缀答案推出来。

三、维护动态集合的顺序信息：单调栈

单调栈解决的是"每个元素左边（或右边）第一个比它大（或小）的元素在哪里"这类问题。

增量方式是：从左到右扫描，每来一个新元素，把栈里所有比它小的元素弹出（因为对未来的元素来说，新元素离得更近且更大，旧元素永远不可能成为"第一个更大"的答案）。弹出时可以立刻为被弹出的元素记录答案。每个元素同样只入栈、出栈各一次，O(n)。

单调栈与单调队列的区别在于：栈只在一端操作，没有"过期"的概念，淘汰的理由纯粹是单调性；队列在两端操作，同时处理单调性和过期两个约束。

四、维护动态集合的统计信息：差分数组

差分数组 D 中，D[i] = nums[i] - nums[i-1]。它把"对区间 [l,r] 整体加一个值"这个操作从 O(n) 降到 O(1)：只需修改 D[l] 和 D[r+1] 两个端点。最后对 D 求一次前缀和还原原数组。

差分数组的增量思想体现在：不记录绝对值，只记录"变化量"。区间修改变成了端点修改，查询时再通过前缀和还原。它是前缀和的逆操作，两者互为对偶。

五、维护动态集合的区间信息：线段树与树状数组

当数组会被动态修改（单点更新），同时需要频繁查询区间统计信息（区间求和、区间最大值），前缀和数组就失效了，因为一次修改会让所有后续前缀和失效，重建代价 O(n)。

树状数组（BIT）的增量方式是：把数组下标按二进制分组，每个节点管理一段特定长度的区间。单点更新时，只沿着一条长度为 O(log n) 的链向上修改相关节点；区间查询时，把区间拆成 O(log n) 段分别读取。每次操作只改动"受影响的部分"，而不是全部重算。

线段树是更通用的版本，支持区间更新和更复杂的聚合函数，代价是常数更大。两者的共同本质是：把"全局信息"分层存储，使得局部变化只影响 O(log n) 个节点。

六、维护动态连通性：并查集

并查集维护的是"哪些元素属于同一个集合"这个信息。每次合并两个集合时，不重新扫描所有元素，而是只修改根节点的指向，O(1) 完成合并。查询时通过路径压缩，把沿途所有节点直接指向根，使得下次查询更快。

它的增量性体现在：每次只处理"新增的一条连接"，历史信息通过树形结构保留，不需要重新计算整个连通关系。

七、维护动态规划的转移：各类 DP 优化

很多 DP 的转移方程形如 dp[j] = max(dp[i] + cost(i,j))，暴力枚举 i 是 O(n²)。如果 cost(i,j) 有某种结构，可以用增量方式维护候选的 dp[i]，避免每次从头枚举。

单调队列优化 DP 就是这个思想的直接应用（你刚学的那道题本质上就是一个 DP）。斜率优化 DP 把候选点维护在一条凸包上，每次新的右端点只需要在凸包上做一次二分或直线扫描，而不是遍历所有历史候选点。

总结：增量维护的统一模式

所有以上结构，都可以用同一套框架来理解。首先是信息的分解，把"全局答案"拆成"历史信息"加"当前新增信息"两部分。其次是历史信息的组织，用某种结构（队列、栈、树、并查集）存储历史信息，使得查询 O(1) 或 O(log n)。最后是增量更新，每来一个新元素，只更新"受影响的部分"，淘汰"永远不再有用的部分"。

认清"什么信息需要维护"以及"什么信息可以提前淘汰"，是从暴力到增量优化的核心判断。你在单调队列里学到的"更小的前缀和且下标更靠右，旧的永远不再有用"，正是这个判断在具体问题上的实例化。