算法笔记：区间内的区间最值问题

1. 核心定义与根本思维

问题描述：
给定一个数组，定义子区间 $[l, r]$ 的某种属性为 $f(l, r)$（例如子段和、子段平均值、子段最大公约数等）。
多次查询：给定大区间 $[i, j]$，求该区间内部所有可能的子区间 $[l, r]$ 中，$f(l, r)$ 的最大值。

根本思维：
这类问题的核心在于 信息的拼接。
既然无法在查询时遍历所有子区间，我们需要将大区间拆分为小区间（分治思想），而解决问题的关键在于：如何利用“左半边”和“右半边”的信息，推导出“跨越中点”的子区间信息。

统一口诀：
“答案要么在左边，要么在右边，要么跨越中间。”

2. 三大考题分类

根据 $f(l, r)$ 的数学性质，这类问题可以分为三个层级，解法由简入繁：

分类一：局部类

特征：$f(l, r)$ 的数学性质决定了，最优解的长度一定很短，或者只与极少数元素有关。
典型例子：最大子段平均值（长度至少为 2）。
- 数学原理：任何一个长子段的平均值，都不会超过其切分出的长度为 2 或 3 的子段的平均值。
解法：转化 + ST表。
- 因为最优解长度极短（如只有 2 或 3），我们不需要看长区间。
- 构造一个新数组，存储每个位置起始的长度为 2 和 3 的平均值的最大值。
- 原问题转化为查询新数组在指定范围内的最大值。
复杂度：预处理对数级，查询常数级。

分类二：可合并类

这是最经典、最通用的类型，常被称为最大子段和变体问题。
* 特征：$f(l, r)$ 满足结合律，可以通过维护边界信息进行合并。
* 典型例子：最大子段和。
* 解法：线段树。
* 核心思维：为了求某区间的最大子段和，仅知道左右儿子的最大子段和是不够的。必须维护“挂在左边界的最大值”和“挂在右边界的最大值”，才能处理跨越中点的情况。
* 合并逻辑：
1. 当前区间答案 = max(左儿子答案, 右儿子答案, 左儿子后缀最大值 + 右儿子前缀最大值)
2. 当前前缀最大值 = max(左儿子前缀最大值, 左儿子总和 + 右儿子前缀最大值)
3. 当前后缀最大值 = max(右儿子后缀最大值, 右儿子总和 + 左儿子后缀最大值)
* 复杂度：建树线性级，查询对数级。

分类三：极值贡献类

特征：$f(l, r)$ 的值强烈依赖于区间内的最小值或最大值作为系数。
典型例子：求所有子区间中，“区间最小值乘以区间和”的最大值。
解法：分治或笛卡尔树。
- 这类问题通常难以像线段树那样直接合并。
- 分治法：对于当前区间，找到最小值所在位置作为切分点，答案可能在切分点左侧、右侧，或者必须包含切分点（利用切分点是最小值这一性质进行扩展）。
复杂度：通常为线性对数级。

3. 根本思维的统一图解

所有这类问题，在设计数据结构时，本质上都在填补以下公式：

$$ 区间答案 = \max \begin{cases} 左区间答案 & (\text{最优解完全在左边}) \ 右区间答案 & (\text{最优解完全在右边}) \ \mathbf{跨越合并}(左信息, 右信息) & (\text{最优解跨越中间}) \end{cases} $$

对于局部类：跨越合并项不存在或被数学性质证明不需要。
对于可合并类：跨越合并项 = 左区间的后缀最大值 + 右区间的前缀最大值。
对于极值贡献类：跨越合并项极其复杂，通常需要利用单调性进行扫描。

4. 总结对照表

分类	核心特征	根本解法	维护的信息
局部类	最优解长度很短	ST表	仅需预处理局部短区间的最大值
可合并类	具有可加性或结合律	线段树	区间和、前缀最大值、后缀最大值、当前答案
极值贡献类	依赖区间极值	分治	极值位置、区间前缀和