前缀和的定义如下:
s[0]=0s[0] = 0s[0]=0
s[i]=a[0]+a[1]+a[2]+...+a[i−1]s[i] = a[0]+a[1]+a[2]+...+a[i-1]s[i]=a[0]+a[1]+a[2]+...+a[i−1]
有了前缀和数组,我们可以用O(1)O(1)O(1)的时间计算区间[r, l]
的和:
s[r+1]−s[l]s[r+1]-s[l] s[r+1]−s[l]
public int preSum(int[] a, int l, int r){
int n = a.length;
int[] s = new int[n+1];
// 计算前缀和数组
for(int i = 1; i <= n; i++){
s[i] = s[i-1] + a[i-1];
}
return s[r+1] - s[l];
}
计算公式
s[i][j]=s[i−1][j]+s[i][j−1]−s[i−1][j−1]+a[i−1][j−1]s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i-1][j-1] s[i][j]=s[i−1][j]+s[i][j−1]−s[i−1][j−1]+a[i−1][j−1]
区间[x1, y1]
到[x2,y2]
和:
s[x2+1][y2+1]−s[x2+1][y1]−s[x1][y2+1]+s[x1][y1]s[x2+1][y2+1]-s[x2+1][y1]-s[x1][y2+1]+s[x1][y1] s[x2+1][y2+1]−s[x2+1][y1]−s[x1][y2+1]+s[x1][y1]
public int preSum(int[][] a, int x1, int y1, int x2, int y2){
int m = a.length;
int n = a[0].length;
int[][] s = new int[m+1][n+1];
for(int i = 1; i <= m; i++){
for(int j = 1; j <= n; j++){
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i-1][j-1];
}
}
return s[x2+1][y2+1]-s[x2+1][y1]-s[x1][y2+1]+s[x1][y1];
}
对于a数组来说,定义一个数组b,使得b的前缀和等于a,b就是a的差分数组。
想要对a数组区间[l, r]
加c,只需要
b[l]+=c,b[r]+=cb[l]+=c,b[r]+=c b[l]+=c,b[r]+=c
tip:此处数组中1开始
class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] a = new int[n+1];
int[] b = new int[n+2]; // 得多开一个空间
for(int i = 1; i <= n; i++){
a[i] = scanner.nextInt();
}
// 构造b数组
for(int i = 1; i <= n; i++){
new Main().insert(b, i, i, a[i]);
}
while((m--) != 0){
int l = scanner.nextInt();
int r = scanner.nextInt();
int c = scanner.nextInt();
new Main().insert(b, l, r, c);
}
for(int i = 1; i <= n; i++){
a[i] = b[i] + a[i-1];
System.out.print(a[i]+" ");
}
}
// 给a数组区间[l, r]加上c
public void insert(int[] b, int l, int r, int c){
b[l] += c;
b[r+1] -= c;
}
}
对[x1, y1]
到[x2, y2]
这个矩形所围的区域加上C,它的差分矩阵就该进行如下操作。
b[x1][y1]+=cb[x1][y1]+=c b[x1][y1]+=c
b[x2+1][y1]−=cb[x2+1][y1]-=c b[x2+1][y1]−=c
b[x1][y2+1]−=cb[x1][y2+1]-=c b[x1][y2+1]−=c
b[x2+1][y2+1]+=cb[x2+1][y2+1]+=c b[x2+1][y2+1]+=c
最后通过b的前缀和就能够还原a。
tip: 此处数组从1开始
class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int q = scanner.nextInt();
int[][] a = new int[n+1][m+1];
int[][] b = new int[n+2][m+2];
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
a[i][j] = scanner.nextInt();
// 构造差分矩阵
new Main().insert(b, i, j, i, j, a[i][j]);
}
}
while((q--) != 0){
int x1 = scanner.nextInt();
int y1 = scanner.nextInt();
int x2 = scanner.nextInt();
int y2 = scanner.nextInt();
int c = scanner.nextInt();
new Main().insert(b, x1, y1, x2, y2, c);
}
// 计算b矩阵的二维前缀和,即a
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
a[i][j] = a[i-1][j] + a[i][j-1] - a[i-1][j-1] + b[i][j];
System.out.print(a[i][j] + " ");
}
System.out.println();
}
}
public void insert(int[][] b, int x1, int y1, int x2, int y2, int c){
b[x1][y1] += c;
b[x2+1][y1] -= c;
b[x1][y2+1] -= c;
b[x2+1][y2+1] += c;
}
}
我们知道两个前缀和相减能够得到一个连续数组的和,比如s[i+1]-s[j]
就表示[j, i]
的区间和。
求出数组的前缀和,用i遍历前缀和数组,如果有i之前的元素j能够使得s[i]-s[j]=k
,则说明[j, i-1]
是一个满足条件的子数组,我们只需要统计之前等于s[j]=s[i]-k
的元素个数就是当前满足条件的子数组个数。
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
int[] s = new int[nums.length + 1];
for(int i = 1; i < s.length; i++){
s[i] = s[i-1] + nums[i-1];
}
int count = 0;
for(int i = 0; i < s.length; i++){
int j = s[i] - k;
if(map.containsKey(j)){
count += map.get(j);
}
map.put(s[i], map.getOrDefault(s[i], 0) + 1);
}
return count;
}
}
我们要判断的是(s[j] - s[i]) % K
是否等于0。那么根据同余定理,(s[j] - s[i]) % K = s[j] % K - s[i] % K
,所以,若要(s[j] - s[i] )% K = 0
只要 s[j] % K = s[i] % K
,我们对前缀和都mod上K,如果s[i]==s[j],i<j
,则说明区间[j-1, i]
和能够被K整除,我们统计这样的元素对数即为答案。
class Solution {
public int subarraysDivByK(int[] A, int K) {
int n = A.length;
int[] s = new int[n+1];
Map<Integer, Integer> map = new HashMap<>();
for(int i = 1; i <= n; i++){
s[i] = s[i-1] + A[i-1];
// 让负数的余数转为正数
s[i] = (s[i]%K + K) % K;
}
int count = 0;
for(int i = 0; i <= n; i++){
if(map.containsKey(s[i])){
count += map.get(s[i]);
}
map.put(s[i], map.getOrDefault(s[i], 0) + 1);
}
return count;
}
}