湘潭seo_前缀和以及差分看这一篇就够了

前缀和以及差分问题:

导论:

该博客纪录前缀和问题以及差分的解题步骤与响应公式;

明了其中转变,有不完善的地方逐步补全;

若是有错误迎接指出!

前缀和:

首先需要知道前缀和的观点:即数组该位置之前的元素之和。

另有一个主要的点,在举行前缀和的运算时,下标从1最先,设数组a[0]=0;

好比a[5] = {0,1,2,3,4};

求a[1]的前缀和:a[1];

求a[2]的前缀和:a[1]+a[2];

……

为什么下标要从1 最先:为了利便后面的盘算,制止下标转换,设为零,不影响效果

前缀和的作用: 快速求出元素组中某段区间的和

一维数组的前缀和问题:

求数组a中(l,r)区间的和 —>用到前缀和

  1. 需要界说两个数组,第一个为原始数组(a[]),第二个为前缀和数组(s[])

    //初始化原数组
    int[] arr = new int[x];
    for (int i = 1; i <= n; i++) {
    	arr[i] = sc.nextInt();
    }
    
  2. 公式:s[i] = s[i-1]+a[i] {其中s[i]示意a数组的前i项的和}

    //前缀和的盘算
    int[] s = new int[x];
    for (int i = 1; i <=n ; i++) {
    	s[i] = s[i-1]+arr[i];
    }
    
  3. 输入区间局限(l,r),s[r]-s[l-1]的效果就是所求区间的和

    sum[r] =a[1]+a[2]+a[3]+a[l-1]+a[l]+a[l+1]......a[r];
    sum[l-1]=a[1]+a[2]+a[3]+a[l-1];
    
    sum[r]-sum[l-1]=a[l]+a[l+1]+......+a[r];
    
    while (m-- !=0){
        int l = sc.nextInt();
        int r = sc.nextInt();
        System.out.println(s[r]-s[l-1]);
    }
    

二维数组的前缀和问题:

方式与一维数组大要相同:需要中心数组s[i][j]

  1. 界说两个二维数组,第一个为原始数组a[][],第二个为暂且数组b[][]

    // 初始化原始数组
    int[][] arr = new int[n+1][m+1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <=m ; j++) {
        	arr[i][j] = sc.nextInt();
        }
    }
    
  2. 公式:s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + arr[i][j]

    湘潭seo_前缀和以及差分看这一篇就够了插图

    //界说s二维数组,求解前缀和s数组
    int[][] s = new int[n+1][m+1];
    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];
        }
    }
    
  3. 输入区间局限(x1,y1,x2,y2),s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]的效果就是所求区间的和;湘潭seo_前缀和以及差分看这一篇就够了插图1

    //求解前缀和
    while(q-- !=0){
        int x1 = sc.nextInt();
        int y1 = sc.nextInt();
        int x2 = sc.nextInt();
        int y2 = sc.nextInt();
        int res = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
        System.out.println(res);
    }
    

差分问题:

首先明了差分的观点:差分实在就是前缀和的逆运算

差分的作用:若是对某个区间需要每个元素加上C则需要使用差分来削减时间复杂度

差分的重点是:组织暂且数组b[]

b[1] = a[1]
b[2] = a[2] - a[1]
b[3 ]= a[3] - a[2]
...
b[n] = a[n] - a[n-1]

两个数组:S[],b[],S[]称为b[]的前缀和,b[]称为S[]的差分

差分的下标也是从1最先

前缀和差分是2个互逆的运算,假设最最先的数组是a[i], 则前缀和数组sum[i]示意从a[1]+..+a[i];而差分数组b[1]+…+b[i]则示意a[i],即a[i]是差分数组b[i]的前缀和;

一维数组的差分问题:

  1. 首先初始化数组s[]

    int[] b = new int[x];
    for (int i = 1; i <=n ; i++) {
        s[i] = sc.nextInt();
    }
    
  2. 根据上面组织数组方式组织b[]数组,公式:b[i] = s[i]-s[i-1]

    //组织差分数组
    for (int i = 1; i <=n ; i++) {
        b[i] = s[i]-s[i-1];
    }
    
  3. 将所求区间(l,r)在b[]数组划分出来并加上c,公式:b[l] +=c,b[r+1] -=c;

    int l,r,c;
    l = sc.nextInt();
    r = sc.nextInt();
    c = sc.nextInt();
    b[l] +=c;
    b[r+1] -=c;
    

    由于s[]数组是b[]数组的前缀和,b[]是s[]的差分,所以在b[]的某个区间上+c会影响的a区间上的效果

    湘潭seo_前缀和以及差分看这一篇就够了插图2

  4. 将差分数组转换成原数组,也就是求差分数组的前缀和,公式:b[i] = b[i-1] +b[i] //类比于s[i]=s[i-1]+a[i]

    for (int i = 1; i <=n ; i++) {
        b[i] = b[i-1]+b[i];
        System.out.print(b[i]+" ");
    }
    

二维数组的差分问题:

记着:a[][]数组是b[][]数组的前缀和数组,那么b[][]a[][]的差分数组

二维差分的焦点也是组织差分数组b[][],使得a数组中a[i][j]是b数组左上角(1,1)到右下角(i,j)所笼罩矩形元素的和;

怎么让子矩阵中的每个元素加上c;

湘潭seo_前缀和以及差分看这一篇就够了插图3

先界说一个函数:

public static void insert(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;
}
  1. 初始化原数组a[][]

    for (int i = 1; i <=n; i++) {
        for (int j = 1; j <=m ; j++) {
            a[i][j] = sc.nextInt();
        }
    }
    
  2. 组织差分数组

    初始化B数组从[1][1][i][j]添加元素,就是将a[][]中的元素遍历到B数组中

    int[][] b = new int[x][x];
    for (int i = 1; i <=n; i++) {
        for (int j = 1; j <=m ; j++) {
            insert(i,j,i,j,a[i][j]);
        }
    }
    
  3. 输入矩形中需要+c的局限(x1,y1)(x2,y2),在差分数组b[][]中找到响应的局限+c

    while (q-- != 0){
        int x1,y1,x2,y2;
        x1 = sc.nextInt();
        y1 = sc.nextInt();
        x2 = sc.nextInt();
        y2 = sc.nextInt();
        int c = sc.nextInt();
        insert(x1,y1,x2,y2,c);
    }
    
  4. b[][]数组中的前缀和–>a[][];公式:b[i][j]=a[i][j]−a[i−1][j]−a[i][j−1]+a[i−1][j−1]

    for (int i = 1; i <=n ; i++) {
        for (int j = 1; j <=m ; j++) {
            b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + b[i][j];
            System.out.print(b[i][j]+" ");
        }
    }
    
  5. 直接输出b[][]中的元素就是a[][]数组中局限所需要+c的效果

竣事:

谢谢列位能看到最后