题目描述 -- 矩阵操作问题

这是一道信息学奥赛模板题。给定一个初始全为零的n×m矩阵A，需要完成以下两种操作：

1. 单点增加操作：1 x y k - 将矩阵元素A[x][y]的值增加k
2. 子矩阵求和操作：2 a b c d - 查询左上角坐标为(a,b)，右下角坐标为(c,d)的子矩阵中所有元素的和

输入格式

第一行包含两个正整数n和m，表示矩阵的行数和列数

接下来若干行，每行一个操作指令，直到文件结束。操作指令格式为： • 1 x y k（单点增加） • 2 a b c d（子矩阵求和）

输出格式

对于每个子矩阵求和操作（类型2），输出一行表示该子矩阵的元素和

2 2
1 1 1 3
1 2 2 4
2 1 1 2 2

7

数据范围与提示

数据规模

• 10%的数据：n = 1（矩阵只有一行） • 10%的数据：m = 1（矩阵只有一列） • 全部数据： • 1 ≤ n, m ≤ 2¹² • 1 ≤ x, a, c ≤ n • 1 ≤ y, b, d ≤ m • |k| ≤ 10⁵ • 操作总数不超过3×10⁵ • 保证所有查询的子矩阵都存在

提示

• 矩阵元素初始值全为0 • 注意大数据量下的算法效率 • 子矩阵坐标保证满足：a ≤ c且b ≤ d

算法建议

这个问题可以使用以下数据结构高效解决：

1. 二维树状数组：支持O(log n × log m)的单点修改和子矩阵查询
2. 二维线段树：支持类似操作但实现更复杂
3. 前缀和数组：仅适用于静态矩阵或修改很少的情况