一维前缀和
S[i] = a[1] + a[2] + ... a[i]
a[l] + ... + a[r] = S[r] - S[l - 1]
final static int N=100010; public static void main(String[] args) { int []arr=new int[N]; int []sum=new int[N]; Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int m=sc.nextInt(); for (int i = 1; i <=n; i++) { arr[i]= sc.nextInt(); } for (int i = 1; i <=n; i++) { sum[i]=sum[i-1]+arr[i]; } while (m--!=0){ int l=sc.nextInt(); int r=sc.nextInt(); System.out.println(sum[r]-sum[l-1]); } }
二维前缀和（子矩阵求和）
S[i, j] = 第i行j列格子左上部分所有元素的和
以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]
final static int N=1010,M=1010; public static void main(String[] args) { int [][]arr=new int[N][M]; int [][]s=new int[N][M]; Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int m=sc.nextInt(); int q=sc.nextInt(); for (int i = 1; i <=n; i++) { for (int j =1; j <=m; j++) { arr[i][j]= sc.nextInt(); } } for (int i = 1; i <=n; i++) { for (int j = 1; j <=m; j++) { s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+arr[i][j]; } } while (q--!=0){ int x1=sc.nextInt(); int y1=sc.nextInt(); int x2=sc.nextInt(); int y2=sc.nextInt(); System.out.println(s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]); } }
一维差分
给区间[l, r]中的每个数加上c：B[l] += c, B[r + 1] -= c
final static int N=100010; static int [] s=new int[N]; public static void main(String[] args) { int []arr=new int[N]; Scanner sc=new Scanner(System.in); int n=sc.nextInt(),m= sc.nextInt(); for (int i = 1; i <=n; i++) { arr[i]= sc.nextInt(); } for (int i = 1; i <=n; i++) { insert(i,i,arr[i]); } while (m--!=0){ int l=sc.nextInt(),r=sc.nextInt(),c=sc.nextInt(); insert(l,r,c); } for (int i=1; i <=n; i++) s[i]+=s[i-1]; for(int i=1;i<=n;i++) System.out.print(s[i]+" "); System.out.println(); } public static void insert(int l,int r,int c){ s[l]+=c; s[r+1]-=c; }
二维差分
给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c
final static int N=1010; static int [][]S=new int[N][N]; public static void main(String[] args) { Scanner sc=new Scanner(System.in); int [][]arr=new int[N][N]; int n= sc.nextInt(),m= sc.nextInt(),q= sc.nextInt(); for (int i =1; i <=n; i++) { for (int j =1; j <=m; j++) { arr[i][j]= sc.nextInt();//读入原始数组 insert(i,j,i,j,arr[i][j]);//构建差分数组S } } while (q-->0){ int x1= sc.nextInt(),y1= sc.nextInt(),x2= sc.nextInt(),y2= sc.nextInt(),c= sc.nextInt(); insert(x1,y1,x2,y2,c); } for (int i =1; i <=n; i++) { for (int j =1; j <=m; j++) { S[i][j]+=S[i][j-1]+S[i-1][j]-S[i-1][j-1];//求差分数组的前n项和 System.out.print(S[i][j]+" ");//输出最后结果 } System.out.println(); } } public static void insert(int x1,int y1,int x2,int y2,int c){ S[x1][y1]+=c; S[x2+1][y1]-=c; S[x1][y2+1]-=c; S[x2+1][y2+1]+=c; }
