中国建设基础设施总公司 网站,网页设计企业网站素材库,网站SEO做点提升流量象客,免费网站营销计划✨个人主页#xff1a;bit me ✨当前专栏#xff1a;算法基础 #x1f525;专栏简介#xff1a;该专栏主要更新一些基础算法题#xff0c;有参加蓝桥杯等算法题竞赛或者正在刷题的铁汁们可以关注一下#xff0c;互相监督打卡学习 #x1f339; #x1f339; #x1f3… ✨个人主页bit me ✨当前专栏算法基础 专栏简介该专栏主要更新一些基础算法题有参加蓝桥杯等算法题竞赛或者正在刷题的铁汁们可以关注一下互相监督打卡学习 前 缀 和 与 差 分 一. 前缀和一维二. 子矩阵的和二维三. 差分四. 差分矩阵五. 总结一. 前缀和一维 输入一个长度为 n 的整数序列。 接下来再输入 m 个询问每个询问输入一对 l,r。 对于每个询问输出原序列中从第 l 个数到第 r 个数的和。 输入格式 第一行包含两个整数 n 和 m。 第二行包含 n 个整数表示整数数列。 接下来 m 行每行包含两个整数 l 和 r表示一个询问的区间范围。 输出格式 共 m 行每行输出一个询问的结果。 数据范围 1 ≤ l ≤ r ≤n, 1 ≤ n,m ≤ 100000, −1000 ≤ 数列中元素的值 ≤ 1000 输入样例 5 3 2 1 3 6 4 1 2 1 3 2 4 输出样例 3 6 10 思路 数组 a[1] a[2] … a[i]对于某一个区间[l,r]的和就是s[r]-s[l-1]考虑边界统一问题可以让 s[0] 0 统一格式但是我们题解可以让边界从角标 1 开始有效避免让 s[0] 0 来单独处理 题解
把数都遍历到数组里
Scanner scan new Scanner(System.in);
int n scan.nextInt();
int m scan.nextInt();
int[] a new int[n1];
int[] s new int[n1];
for(int i 1 ; i n ; i ){a[i] scan.nextInt();
}前 n 项数组和
for(int i 1 ; i n ; i ){s[i] s[i-1] a[i];
}根据规律某一个区间[l,r]的和就是s[r]-s[l-1]
while(m-- 0){int l scan.nextInt();int r scan.nextInt();System.out.println(s[r] - s[l-1]);
}附上总的代码
import java.util.Scanner;
public static void main(String[] args){Scanner scan new Scanner(System.in);int n scan.nextInt();int m scan.nextInt();int[] a new int[n1];int[] s new int[n1];for(int i 1 ; i n ; i ){a[i] scan.nextInt();}for(int i 1 ; i n ; i ){s[i] s[i-1] a[i];}while(m-- 0){int l scan.nextInt();int r scan.nextInt();System.out.println(s[r] - s[l-1]);}
}二. 子矩阵的和二维 输入一个 n 行 m 列的整数矩阵再输入 q 个询问每个询问包含四个整数x1,y1,x2,y2表示一个子矩阵的左上角坐标和右下角坐标。 对于每个询问输出子矩阵中所有数的和。 输入格式 第一行包含三个整数 nmq。 接下来 n 行每行包含 m 个整数表示整数矩阵。 接下来 q 行每行包含四个整数 x1,y1,x2,y2表示一组询问。 输出格式 共 q 行每行输出一个询问的结果。 数据范围 1 ≤ n,m ≤1000, 1 ≤ q ≤ 200000, 1 ≤ x1 ≤ x2 ≤n, 1 ≤ y1 ≤ y2 ≤m, −1000 ≤ 矩阵内元素的值 ≤ 1000 输入样例 3 4 3 1 7 2 4 3 6 2 8 2 1 2 3 1 1 2 2 2 1 3 4 1 3 3 4 输出样例 17 27 21 思路 此处视图就不画了我们要先了解清楚计算的公式 s[i,j] s[i - 1,j] s[i,j - 1] - s[i - 1,j - 1] a[i,j](x1, y1),(x2, y2) 这一矩阵中所有数的和 s[x2,y2] - s[x2,y1 - 1] - s[x1 - 1,y2] s[x1 - 1,y1 - 1] 题解
继续按照上题一样角标都从 1 开始因此数组都要扩容 1
Scanner scan new Scanner(System.in);
int n scan.nextInt();
int m scan.nextInt();
int q scan.nextInt();
int[][] a new int[n1][m1];
int[][] s new int[n1][m1];
for(int i 1 ; i n ; i ){for(int j 1 ;j m ; j ){a[i][j] scan.nextInt();}
}按照思路计算二维数组每一块从 (1,1) 到 (i,j) 的大小得出 s[i,j] 的通式
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] a[i][j];}
}通式计算区域相加减的出的面积
while(q--0){int x1 scan.nextInt();int y1 scan.nextInt();int x2 scan.nextInt();int y2 scan.nextInt();System.out.println(s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] s[x1-1][y1-1]);
}附上总的代码
import java.util.Scanner;
public static void main(String[] args){Scanner scan new Scanner(System.in);int n scan.nextInt();int m scan.nextInt();int q scan.nextInt();int[][] a new int[n1][m1];int[][] s new int[n1][m1];for(int i 1 ; i n ; i ){for(int j 1 ;j m ; j ){a[i][j] scan.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] a[i][j];}}while(q--0){int x1 scan.nextInt();int y1 scan.nextInt();int x2 scan.nextInt();int y2 scan.nextInt();System.out.println(s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] s[x1-1][y1-1]);}
}三. 差分 输入一个长度为 n 的整数序列。 接下来输入 m 个操作每个操作包含三个整数 l,r,c表示将序列中 [l,r] 之间的每个数加上 c。 请你输出进行完所有操作后的序列。 输入格式 第一行包含两个整数 n 和 m。 第二行包含 n 个整数表示整数序列。 接下来 m 行每行包含三个整数 lrc表示一个操作。 输出格式 共一行包含 n 个整数表示最终序列。 数据范围 1 ≤ n,m ≤ 100000, 1 ≤ l ≤ r ≤ n, −1000 ≤ c ≤ 1000, −1000 ≤ 整数序列中元素的值 ≤ 1000 输入样例 6 3 1 2 2 1 2 1 1 3 1 3 5 1 1 6 1 输出样例 3 4 5 3 4 2 思路 差分是求前缀和的逆操作如果想将a数组中 [l,r] 部分的数据全部加上c只需要将 b[l] c然后 b[r1] - c 即可。差分操作和前缀和一样数组下标都从1开始。b[l] c 后l后面的数组都会加 c。r 后面的数据也会被改变要改回来就得 b[r1] - c 求a[i]的值 其实就是求b数组的一位前缀和 题解
先解决范围问题
static int N 1000010;
static int[] a new int[N];
static int[] b new int[N];数据遍历进数组
Scanner scan new Scanner(System.in);
int n scan.nextInt();
int m scan.nextInt();
for(int i 1 ; i n ; i ){a[i] scan.nextInt();
}构造一下b数组,因为a是b数组的前缀和
for(int i 1 ; i n ; i ){b[i] a[i] - a[i - 1];
}将a数组中 [l,r] 部分的数据全部加上c
while(m -- 0){int l scan.nextInt();int r scan.nextInt();int c scan.nextInt();b[l] c;b[r 1] - c;
}最后求一遍差分数组的前缀和
for(int i 1 ; i n ; i ){b[i] b[i - 1];System.out.print(b[i] );
}附上总的代码
import java.util.*;public class Test {static int N 1000010;static int[] a new int[N];static int[] b new int[N];public static void main(String[] args){Scanner scan new Scanner(System.in);int n scan.nextInt();int m scan.nextInt();for(int i 1 ; i n ; i ){a[i] scan.nextInt();}for(int i 1 ; i n ; i ){b[i] a[i] - a[i - 1];}while(m -- 0){int l scan.nextInt();int r scan.nextInt();int c scan.nextInt();b[l] c;b[r 1] - c;}for(int i 1 ; i n ; i ){b[i] b[i - 1];System.out.print(b[i] );}}
}四. 差分矩阵 输入一个 n 行 m 列的整数矩阵再输入 q 个操作每个操作包含五个整数x1,y1,x2,y2,c其中 (x1,y1) 和 (x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。 每个操作都要将选中的子矩阵中的每个元素的值加上 c。 请你将进行完所有操作后的矩阵输出。 输入格式 第一行包含整数 n,m,q。 接下来 n 行每行包含 m 个整数表示整数矩阵。 接下来 q 行每行包含 5 个整数 x1,y1,x2,y2,c表示一个操作。 输出格式 共 n 行每行 m 个整数表示所有操作进行完毕后的最终矩阵。 数据范围 1 ≤ n,m ≤ 1000, 1 ≤ q ≤ 100000, 1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ m, −1000 ≤ c ≤ 1000, −1000 ≤ 矩阵内元素的值 ≤ 1000 输入样例 3 4 3 1 2 2 1 3 2 2 1 1 1 1 1 1 1 2 2 1 1 3 2 3 2 3 1 3 4 1 输出样例 2 3 4 1 4 3 4 1 2 2 2 2 思路 对差分数组操作 b[x1][y1] c; b[x1 -1][y2] - c;b[x2][y1 -1] - c; b[x2 - 1][y2 - 1] c;求a的差分数组bb[i][j] a[i][j] - a[i - 1][j] - a[i][j - 1] a[i - 1][j - 1]; 题解
创建原数组 同时也是b的前缀和数组a的差分数组
canner sc new Scanner (System.in);
int n sc.nextInt() , m sc.nextInt(), q sc.nextInt();
int[][] a new int[1010][1010];//原数组 同时也是b的前缀和数组
int[][] b new int[1010][1010];//a的差分数组
for(int i 1;i n; i ) {for(int j 1; j m; j ) {a[i][j] sc.nextInt();}
}求a的差分数组b
for(int i 1;i n; i ) {for(int j 1; j m; j ) {b[i][j] a[i][j] - a[i - 1][j] - a[i][j - 1] a[i - 1][j - 1];}
}对差分数组操作
for(int i 0; i q; i ) {int x1 sc.nextInt(),y1 sc.nextInt(),x2 sc.nextInt(),y2 sc.nextInt() ,c sc.nextInt();b[x1][y1] c;b[x2 1][y1] - c;b[x1][y2 1] - c;b[x2 1][y2 1] c;
}再对b数组求一遍前缀和数组 并输出
for(int i 1;i n; i ) {for(int j 1; j m; j ) {a[i][j] b[i][j] a[i - 1][j] a[i][j - 1] - a[i - 1][j - 1];System.out.print(a[i][j] );}System.out.println();
}附上总的代码
import java.util.*;
public class Main{
public static void main(String[] args) {Scanner sc new Scanner (System.in);int n sc.nextInt() , m sc.nextInt(), q sc.nextInt();int[][] a new int[1010][1010];int[][] b new int[1010][1010];for(int i 1;i n; i ) {for(int j 1; j m; j ) {a[i][j] sc.nextInt();}}for(int i 1;i n; i ) {for(int j 1; j m; j ) {b[i][j] a[i][j] - a[i - 1][j] - a[i][j - 1] a[i - 1][j - 1];}}for(int i 0; i q; i ) {int x1 sc.nextInt(),y1 sc.nextInt(),x2 sc.nextInt(),y2 sc.nextInt() ,c sc.nextInt();b[x1][y1] c;b[x2 1][y1] - c;b[x1][y2 1] - c;b[x2 1][y2 1] c;}for(int i 1;i n; i ) {for(int j 1; j m; j ) {a[i][j] b[i][j] a[i - 1][j] a[i][j - 1] - a[i - 1][j - 1];System.out.print(a[i][j] );}System.out.println();}
}
}五. 总结
简单的对于一维、二维以及三维的前缀和和差分的计算公式做一个简单的整理 这里要知道对于n维的前缀和或者差分有 2^n 项
前缀和 一维前缀和 s[i] s[i-1] a[i] 求[l, r]区间的和s[r] - s[l-1] 二维前缀和s[i][j] s[i-1][j] s[i][j-1] - s[i-1][j-1] a[i][j] 求[x1, y1] 到 [x2, y2]的和 s[x2][y2] - s[x1-1][y2] s[x2][y1-1] - s[x1-1][y1-1] 差分 一维差分 将[l, r]上的所有数c :b[l] c , b[r1] - c 求a[i]的值 其实就是求b数组的一位前缀和 二维差分 将[x1, y1]到[x2, y2]上的数字c: b[x1][x2]c , b[x21][y1] - c , b[x1][y21] -c , b[x21][y21] c 求a[i]的值: 其实就是求b数组的二维前缀和
