# 合并修改，再建立静态查询结构

Codex（GPT-6）：利用最多20段连续修改的条件，设计二维差分与紧凑静态二维线段树的组合、证明、实现和检验。首选程序为 [std.cpp](std.cpp)。出题人尝试的二维线段树保留为静态查询组件；不能把其不完整的跨维懒标记直接当作正确的动态方案。

## 为什么按段处理

一个连续修改段内部没有查询，可以交换其中各次加法的顺序，并把它们累积到二维差分数组。对于半开矩形 $[x_1,x_2)\times[y_1,y_2)$ ，在四角分别加 $v,-v,-v,v$ .越过矩阵下边或右边的角无需保存。

第一次遇到查询时，计算二维前缀和，把累积增量加入当前单元值，再清零差分。重建一次静态矩形最大值结构。此后的连续查询复用该结构，直到下一个修改段。开头若直接查询，需要一次初始建树；末尾若只有修改，无需还原。

## 紧凑二维线段树

一维迭代线段树把长度 $k$ 的叶子放在 $[k,2k)$ ，无需补齐二次幂。二维数组大小为 $2n\times2m$ .叶子 $(i+n,j+m)$ 保存单元值；先在每个叶行上向上合并列，再合并行。每个节点保存它所代表的行集合与列集合的笛卡尔积上的最大值。

查询先把行区间分为 $O(\log(n+1))$ 个节点，再在每个行节点上查询列区间，需要 $O(\log(m+1))$ .节点编号的叶序可能环绕，但迭代区间算法选出的叶集合仍恰好是不重不漏的目标区间，最大值合并满足结合律。

## 正确性

四角差分的二维前缀和在目标矩形内贡献 $v$ ，在外部贡献0。线性叠加后，还原所得增量等于这一段所有修改逐个执行的结果。

建树时叶子存真实值，每次合并取两部分最大值，因此所有节点的最大值正确。查询按行和列分割成覆盖目标矩形的互不相交块，取这些块的最大值就是答案。每次查询前若有未处理修改就重建，故始终查询到当前矩阵。

## 不能直接使用的跨维标记

二维懒标记需要同时维护行、列方向的信息，不能只把某个列节点的标记临时借给行孩子。具体反例：全零 $2\times2$ 矩阵，对第一列全部单元加1两次，再查询第一行两列的最大值，应为2。出题人的动态尝试得到0，因为覆盖第一列的标记没有正确贡献到该跨列查询。这个跨维传播缺陷不影响静态二维树的合并不变量；这里仅对静态树作完整使用。

## 复杂度与数值范围

设修改段数为 $U\le20$ .每次更新只改四角，总时间为 $O((U+1)nm+Q\log(n+1)\log(m+1))$ ，空间为 $O(nm)$ .

任一单元的绝对值至多 $20000+10^5\cdot20000=2000020000<2^{31}$ ，因此树可以保存32位有符号整数。差分及前缀中间值用64位；主数组约占 $16nm+8nm=24nm$ 字节。查询初值取最小整数，不能取0。普通逐格修改会在大矩形上退化；四维稀疏表的空间也不适合千万格范围。

## 验证与性能

正式数据各运行五次，并单独测量峰值内存。标准程序最慢中位数 1.796455 秒，峰值 234.07 MiB。按2倍向上取整至0.5秒，参考时限为 4 秒。

[测试说明](tests/README.md)、[环境](../../../docs/评测环境与性能.md)及[逐次测量和哈希](../../../docs/benchmark-R35.json)提供复现依据。其他环境需重新校准。