网站做优化每天一定要更新,网站建设的宣传词,网站建设 网页制作,萧涵wordpress主题文章目录 一维前缀和一维前缀和概念一维前缀和数组的构建 二维前缀和二维前缀和概念二维前缀和数组的构建 一维差分一维差分概念一维差分数组的构建 二维差分二维差分概念二维差分数组的构建 一维前缀和
一维前缀和概念
一维前缀和是一种常用的数据预处理方法#xff0c;它能… 文章目录 一维前缀和一维前缀和概念一维前缀和数组的构建 二维前缀和二维前缀和概念二维前缀和数组的构建 一维差分一维差分概念一维差分数组的构建 二维差分二维差分概念二维差分数组的构建 一维前缀和
一维前缀和概念
一维前缀和是一种常用的数据预处理方法它能够在O(1)的时间复杂度内快速求出数组任意子区间的和。这种方法通过构建一个前缀和数组来实现其中每个元素表示从数组开始到当前位置的所有元素的和。
一维前缀和数组的构建
接下来让我们用一道题引入主题
public class Main
{public static void main(String[] args){Scanner in new Scanner(System.in);int nin.nextInt();int qin.nextInt();long[] arrnew long[n1];long[] prenew long[n1];//一维前缀和数组for(int i1;in;i){arr[i]in.nextLong();pre[i]pre[i-1]arr[i];//一维前缀和的构建}while((q--)0){int lin.nextInt();int rin.nextInt();System.out.println(pre[r]-pre[l-1]);//一维前缀和的使用pre[r]-pre[l-1]}}
}一维前缀和题目链接 一维前缀和的构建就是需要求和的前一个元素的前缀和加上求和元素本身。 切记别死记模板 列如这一道题寻找数组的中心下标
class Solution {public int pivotIndex(int[] nums) {int nnums.length;int[] lsumnew int[n];int[] rsumnew int[n];lsum[0]rsum[n-1]0;for(int i1;in;i){lsum[i]lsum[i-1]nums[i-1];}for(int in-2;i0;i--){rsum[i]rsum[i1]nums[i1];}for(int i0;in;i){if(lsum[i]rsum[i]){return i;}}return -1;}
}lsum数组表示的是[0,i-1]区间的前缀和rsum数组表示的是[i1,n-1]区间的前缀和。
一维前缀和的使用pre[r]-pre[l-1]图解
二维前缀和
二维前缀和概念
二维前缀和是一种在二维数组或矩阵中快速计算子矩阵元素和的方法。
二维前缀和数组的构建
在二维数组中我们首先定义一个二维数组dp其中dp[i][j]表示从原数组左上角(1,1)到(i,j)形成的子矩阵的元素和。计算dp[i][j]的状态转移方程如下
dp[i][j] dp[i-1][j] dp[i][j-1] - dp[i-1][j-1] arr[i][j]这个方程的含义是当前元素的前缀和等于其上方和左方元素的前缀和之和减去左上角重叠部分的前缀和再加上当前元素的值。 图解 二维前缀和题目模板
public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别int nin.nextInt();int min.nextInt();int qin.nextInt();int[][] arrnew int[n1][m1];for(int i1;in;i){for(int j1;jm;j){arr[i][j]in.nextInt();}}long[][] dpnew long[n1][m1];for(int i1;in;i){for(int j1;jm;j){dp[i][j]dp[i-1][j]dp[i][j-1]arr[i][j]-dp[i-1][j-1];}}while((q--)0){int x1in.nextInt();int y1in.nextInt();int x2in.nextInt();int y2in.nextInt();System.out.println(dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]dp[x1-1][y1-1]);}}
}二维前缀和的使用dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]dp[x1-1][y1-1]) 一维差分
一维差分概念
对于一个数列 a[i]我们需要维护的数据是“相邻两个数之差”。这种策略是令p[i]a[i]-a[i-1]即相邻两数的差。我们称数列 p[i] 为数列 a[i]的差分数列。差分数列可以快速的在某个区间加上加上或者减去一个数。
一维差分数组的构建
差分可以看成前缀和的逆运算 首先给定一个原数组aa[1], a[2], a[3], a[n]; 然后我们构造一个数组b b[1], b[2], b[3], b[i]; 使得 a[i] b[1] b[2] b[3] , b[i] 1.a[1]b[1]; 2.a[2]b[1]b[2]; 3.a[3]b[1]b[2]b[3]; 由123得 b[1]a[1]; b[2]a[2]-b[1]a[2]-a[1]; b[3]a[3]-b[1]-b[2]a[3]-a[2]; 也就是说a数组是b数组的前缀和数组反过来我们把b数组叫做a数组的差分数组。换句话说每一个a[i]都是b数组中从头开始的一段区间和。 一维差分的构建用p[i]a[i]-a[i-1]即可。 一维差分题目模板
public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);int nin.nextInt();int min.nextInt();int[] arrnew int[n10];for(int i1;in;i){arr[i]in.nextInt();}long[] prenew long[n10];for(int i1;in;i){pre[i]arr[i]-arr[i-1];//建立差分数组}while((m--)0){int lin.nextInt();int rin.nextInt();int kin.nextInt();pre[l]k;//使用差分数组pre[r1]-k;}for(int i1;in;i){pre[i]pre[i-1];//差分数组求前缀和还原为原数组System.out.print(pre[i] );}}
}使用差分数组 pre[l]k; pre[r1]-k;
二维差分
二维差分概念
二维差分是一种数据处理技术应用于二维数组或矩阵中用来快速计算和更新子矩阵元素的和。 它是对一维差分概念的自然扩展旨在简化对二维数据结构中特定区域元素进行加减操作的过程同时保持较高的计算效率。
二维差分数组的构建
由于差分可以看出前缀和的逆运算所以差分数组可以通过前缀和数组求得。
dp[i][j] dp[i-1][j] dp[i][j-1] - dp[i-1][j-1] arr[i][j];//前缀和数组
arr[i][j]dp[i][j]-dp[i-1][j]-dp[i][j-1]dp[i-1][j-1];二维差分题目模板
public class Main {public static void main(String[] args) {Scanner in new Scanner(System.in);int nin.nextInt();int min.nextInt();int qin.nextInt();long[][] arr1new long[n2][m2];long[][] arr2new long[n2][m2];for(int i1;in;i){for(int j1;jm;j){arr1[i][j]in.nextLong();//构建二维差分数组arr2[i][j]arr1[i][j]-arr1[i-1][j]-arr1[i][j-1]arr1[i-1][j-1];}}while((q--)0){int x1in.nextInt();int y1in.nextInt();int x2in.nextInt();int y2in.nextInt();int kin.nextInt();//二维差分的使用arr2[x1][y1]k;arr2[x21][y1]-k;arr2[x1][y21]-k;arr2[x21][y21]k;}long[][] arr3new long[n2][m2];for(int i1;in;i){for(int j1;jm;j){//二维差分数组求前缀和得原数组arr3[i][j]arr3[i-1][j]arr3[i][j-1]-arr3[i-1][j-1]arr2[i][j];System.out.print(arr3[i][j] );}System.out.println();}}
}//二维差分的使用图解arr2[x1][y1]k;arr2[x21][y1]-k;arr2[x1][y21]-k;arr2[x21][y21]k;原数组通过前缀和数组求差分得来。
public class Main12
{public int[] arr1{0,1,2,3,4,5,6,7,8,9,10};int narr1.length;int[] sumnew int[n1];//一维前缀和数组int[] pprenew int[n1];//一维前缀和数组求差分的数组Overridepublic String toString() {return Main12{ sum Arrays.toString(sum) , ppre Arrays.toString(ppre) };}public void sum1(int[] arr2)//一维前缀和{for(int i1;in;i){sum[i]sum[i-1]arr2[i];}}public void ppre(int[] arr1){for(int i1;in;i){ppre[i]sum[i]-sum[i-1];}}public static void main(String[] args) {Main12 main12new Main12();main12.sum1(main12.arr1);main12.ppre(main12.sum);System.out.println(main12.toString());}
}
另外通过差分求原数组大家可以自己试试。
