前缀和

使用一个数组sum来维护原数组a的前缀和，即sum[i] = a[1] + a[2] + ... + a[i]
前缀和其实非常简单，它的用处也无处不在。最主要的进行多次的区间求和，会在很多其他的算法中出现。
例如：求a[l...r]的和，即sum[r] - sum[l - 1]

一维前缀和

static final int N = 100010;
static int[] sum = new int[N];
public static void main(String[] args) {Scanner in = new Scanner(System.in);int n, m;n = in.nextInt();for(int i = 1; i <= n; i ++){int x = in.nextInt();sum[i] = x + sum[i - 1];}m = in.nextInt();while(m --> 0){int l, r;l = in.nextInt();r = in.nextInt();System.out.println(sum[r] - sum[l - 1]);}
}

变形

给你N个数，分别是a[1],a[2],...,a[n]。求一个最长的区间[x,y]，使得区间中的数(a[x],a[x+1],a[x+2],...,a[y-1],a[y])的和能被7整除。输出区间长度。若没有符合要求的区间，输出0。
N (1≤N≤50,0001≤N≤50,000)

import java.util.*;public class Main {static final int N = 100010;static int[] first = new int[]{0, -1, -1, -1, -1, -1, -1}, last = new int[7];public static void main(String[] args) {Scanner in = new Scanner(System.in);int n, sum = 0;n = in.nextInt();for(int i = 1; i <= n; i ++){int x = in.nextInt();sum = sum + x;sum %= 7;if(first[sum] == -1) first[sum] = i;last[sum] = i;}int res = 0;for(int i = 0; i <= 6; i ++){if(first[i] != -1){res = Math.max(last[i] - first[i], res);}}System.out.println(res);}
}

二维前缀和

代码实现：

import java.util.*;public class Main{static final int N = 10000;static int[][] sum = new int[N][N];// sum[i][j]表示的是从(1,1)~(i,j)的子矩阵的和public static void main(String[] args){Scanner in = new Scanner(System.in);int n, m, q;n = in.nextInt();m = in.nextInt();for(int i = 1; i <= n; i ++){for(int j = 1; j <= m;j ++){int w = in.nextInt();sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + w;}}q = in.nextInt();while(q --> 0){int x1, y1, x2, y2;x1 = in.nextInt();y1 = in.nextInt();x2 = in.nextInt();y2 = in.nextInt();System.out.println(sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1]);}}
}

差分

使用d来维护使得a[i] = d[1] + d[2] + d[i]的一个数组。即a是d的前缀和数组。差分与前缀和互为逆运算。
差分用的最多的地方就是，给一个区间的所有数进行多次加减同一个数，最后求改变后的数组。
不论是一维差分还是差分矩阵，我们不需要知道他是如何构造的，只需要知道他是如何修改的就行。并且我们无时无刻都要清楚差分数组的前缀和就是原数组，不论是一维还是二维。

一维差分

代码实现：

static final int N = 100010;
static int[] d = new int[N];
public static void main(String[] args) {Scanner in = new Scanner(System.in);int n;n = in.nextInt();for(int i = 1; i <= n; i ++){int k = in.nextInt();insert(i, i, k);}for(int i = 1; i <= n; i ++){System.out.print(d[i] + " ");}
}
public static void insert(int l, int r, int k){d[l] += k;d[r + 1] -= k;
}

二维差分

代码实现：

import java.util.*;public class Main{static final int N = 10000;static int[][] d = new int[N][N];public static void main(String[] args){Scanner in = new Scanner(System.in);int n, m;n = in.nextInt();m = in.nextInt();// 构造差分矩阵for(int i = 1; i <= n; i ++){for(int j = 1; j <= m; j ++){int x = in.nextInt();add(i, j, i, j, x);}}for(int i = 1; i <= n; i ++){for(int j = 1; j <= m; j ++){System.out.print(d[i][j] + " ");}System.out.println();}}/*** 给(x1,y1)~(x2,y2)的所有数都加上x* @param x1* @param y1* @param x2* @param y2* @param x*/public static void add(int x1, int y1, int x2, int y2, int x){d[x1][y1] += x;d[x1][y2 + 1] -= x;d[x2 + 1][y1] -= x;d[x2 + 1][y2 + 1] += x;}}