我将 LeetCode 304 题改写为了标准的 NOI/CSP 普及组/提高组风格题目，重点考察二维前缀和与容斥原理。

[OI 基础训练] 领主的土地统计 (二维前缀和)

一、 题目背景与知识点讲解

在上一阶段的一维前缀和中，我们解决了线性数组的快速求和问题。现在，问题升级到了二维平面。

场景描述： 给定一个 $N \times M$ 的矩阵（可以想象成一片划分成网格的土地，每个格子里有不同数量的庄稼）。我们需要频繁地查询任意一个矩形子区域内的数字总和。

1. 暴力解法 (Naive Approach) 对于每一次查询 $(x_1, y_1)$ 到 $(x_2, y_2)$，使用双重循环遍历该区域内的所有元素并累加。

• 复杂度：设矩阵大小为 $N \times M$，查询次数为 $Q$。单次查询最坏 $O(N \times M)$。总复杂度 $O(Q \times N \times M)$。
• 后果：当 $N, M=1000, Q=10^5$ 时，计算量高达 $10^{11}$，绝对超时 (TLE)。

2. 优化解法：二维前缀和 (2D Prefix Sum) 我们要利用容斥原理 (Inclusion-Exclusion Principle) 进行预处理。

• 定义： 设 $S[i][j]$ 表示以 $(1, 1)$ 为左上角，$(i, j)$ 为右下角的矩形区域内所有元素的和。

• 递推构造公式 (预处理)： 当我们计算 $S[i][j]$ 时，可以通过“上方区域”加上“左方区域”，减去“左上重叠区域”（因为加了两次），再加上“当前格子”得到。

  $$S[i][j] = S[i-1][j] + S[i][j-1] - S[i-1][j-1] + A[i][j] $$

• 子矩阵求和公式 (查询)： 若要求以 $(x_1, y_1)$ 为左上角，$(x_2, y_2)$ 为右下角的子矩阵和，公式如下：

  $$Sum = S[x_2][y_2] - S[x_1-1][y_2] - S[x_2][y_1-1] + S[x_1-1][y_1-1] $$
  • 直观理解：
    1. 拿走大矩形 $(1,1) \sim (x_2, y_2)$。
    2. 挖掉上方不需要的部分 $(1,1) \sim (x_1-1, y_2)$。
    3. 挖掉左方不需要的部分 $(1,1) \sim (x_2, y_1-1)$。
    4. 此时左上角的那块 $(1,1) \sim (x_1-1, y_1-1)$ 被挖了两次，需要补回来一次。

• 复杂度分析：

  • 预处理：$O(N \times M)$
  • 查询：$O(1)$
  • 总复杂度：$O(N \times M + Q)$，效率极高。

二、 题目描述

在一个遥远的王国里，领主拥有一片巨大的矩形土地。这片土地被划分成了 $N$ 行 $M$ 列的网格，每个网格 $(i, j)$ 内都种植了不同数量的魔法作物 $A_{i,j}$。

领主非常关心收成情况，他会经常向你发出查询指令。每次指令会给出两个坐标 $(x_1, y_1)$ 和 $(x_2, y_2)$，代表一个矩形区域的左上角和右下角。

请你编写一个程序，快速计算出每次查询区域内魔法作物的总数量。

注意：

1. 本题采用 1-based 索引（行号列号从 1 开始）。
2. 矩阵中的数值在后续过程中不会改变。

输入格式

第一行包含三个整数 $N, M, Q$，分别表示土地的行数、列数和查询的次数。 接下来 $N$ 行，每行包含 $M$ 个整数，表示矩阵 $A$ 中的元素。 接下来 $Q$ 行，每行包含四个整数 $x_1, y_1, x_2, y_2$，表示查询区域的左上角坐标 $(x_1, y_1)$ 和右下角坐标 $(x_2, y_2)$。

输出格式

对于每一次查询，输出一行一个整数，表示该矩形区域内元素的和。

数据范围

• $1 \le N, M \le 1000$
• $1 \le Q \le 100,000$
• $-1000 \le A_{i,j} \le 1000$
• $1 \le x_1 \le x_2 \le N$
• $1 \le y_1 \le y_2 \le M$
• 结果保证在 64 位有符号整数 (long long) 范围内。

样例输入

3 4 3
1 2 3 4
5 6 7 8
9 10 11 12
1 1 2 2
2 2 3 3
1 1 3 4

样例输出

14
34
78

样例解释

• 矩阵为：

  1  2  3  4
  5  6  7  8
  9 10 11 12
  

• 查询 1 (1,1) 到 (2,2)：$1+2+5+6 = 14$。
• 查询 2 (2,2) 到 (3,3)：$6+7+10+11 = 34$。
• 查询 3 (1,1) 到 (3,4)：所有元素之和，为 78。

三、 标准代码 (C++14 OI风格)

见题解

四、 教学备课重点 (教练参考)

1. 坐标系的转换：

   • LeetCode 原题是 0-indexed，查询时需要处理复杂的边界（如 row-1 是否小于 0）。
   • OI 技巧：强烈建议在讲解时使用 1-based（从 1 开始）的坐标系。通过在数组外围“多包一层 0”（即第 0 行和第 0 列全是 0），可以完美规避边界判断，公式统一且不易出错。

2. 公式记忆法：

   • 构造时：因为是累加，所以重叠部分被加了两次，要减去一次（$S[i-1][j-1]$）。
   • 查询时：因为是挖洞，减去上方和左方时，左上角被减了两次，要加回来一次（$S[x_1-1][y_1-1]$）。
   • 这两种公式正好符号相反，写成带括号形式会不容易错。

        // 核心查询公式 (容斥原理)：
        // 目标区域 = 大矩形 - 上半部 - 左半部 + 左上角被多减的一次
        //带括号形式符号更容易理解：
        //目标区域 = 大矩形 - (上半部 + 左半部 - 左上角被多减的一次)
        ll ans = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
        // ll ans = s[x2][y2] - (s[x1 - 1][y2] + s[x2][y1 - 1] - s[x1 - 1][y1 - 1]);

3. 空间与时间权衡：

   • 如果内存非常紧张，可以只开一个数组吗？
   • 如果是离线查询，或者只求一次，可以。但如果是频繁查询，必须保留 $O(NM)$ 的前缀和数组。
   • 本题数据 $N, M \le 1000$，数组大小约 $10^6$，long long 占用约 8MB，完全在允许范围内（通常限制 128MB 或 256MB）。

4. 常见错误：

   • 下标越界：在 x1-1 处，如果 x1=0 就会出错。使用 1-based 索引可解决。
   • 坐标搞反：输入是 $(x_1, y_1, x_2, y_2)$，代入公式时不要弄错行和列。
   • 数据溢出：虽然单个元素是 int，但 $1000 \times 1000$ 个 int 累加很容易超过 $2^{31}-1$，必须使用 long long。