差分和前缀和

蓝桥杯第14届中的一道题所学：题目描述
小蓝拥有 n × n 大小的棋盘，一开始棋盘上全都是白子。小蓝进行了 m 次操作，每次操作会将棋盘上某个范围内的所有棋子的颜色取反 (也就是白色棋子变为黑色，黑色棋子变为白色)。请输出所有操作做完后棋盘上每个棋子的颜色。

输入格式
输入的第一行包含两个整数 n, m，用一个空格分隔，表示棋盘大小与操作数。

接下来 m 行每行包含四个整数 x1, y1, x2, y2，相邻整数之间使用一个空格分隔，表示将在 x1 至 x2 行和 y1 至 y2 列中的棋子颜色取反。

输出格式
输出 n 行，每行 n 个 0 或 1 表示该位置棋子的颜色。如果是白色则输出 0，否则输出 1 。

样例输入
3 3
1 1 2 2
2 2 3 3
1 1 3 3
样例输出
001
010
100

单纯遍历去修改很明显超时，看解析了解到差分和前缀和联合起来求解。

对于二维

根据本题感觉应该是看成左上角顶点和（右上后面，左下下面，右下斜下）这些去标记。前缀和就是+=前面+上面-斜上

 1 import java.util.Scanner;
 2 public class Main {
 3     
 4     static int[][] mp;
 5     
 6     public static void main(String[] args) {
 7         Scanner sc = new Scanner(System.in);
 8         int n = sc.nextInt(),m = sc.nextInt();
 9         mp = new int[n + 5][n + 5];
10         
11         while((m--) != 0) {
12             int x1 = sc.nextInt();
13             int y1 = sc.nextInt();
14             int x2 = sc.nextInt();
15             int y2 = sc.nextInt();
16             deal_mp(x1,y1,x2,y2);
17         }
18         pre_sum(n);
19         
20         for(int i = 1; i <= n; ++i) {
21             for(int j = 1; j <= n; ++j) {
22                 if((mp[i][j] & 1) == 0)
23                     System.out.print(0);
24                 else System.out.print(1);
25             }
26             System.out.println();
27             
28         }
29         
30     }
31     
32     private static void pre_sum(int n) {
33         for(int i = 1; i <= n; ++i)
34             for(int j = 1; j <= n; ++j)
35                 mp[i][j] +=  mp[i][j - 1] + mp[i - 1][j] - mp[i - 1][j - 1];
36         
37     }
38 
39 
40     private static void deal_mp(int x1, int y1, int x2, int y2) {
41         mp[x1][y1]++;
42         mp[x1][y2 + 1]++;
43         mp[x2 + 1][y1]++;
44         mp[x2 + 1][y2 + 1]++;
45     }
46 
47 }