2019-11-12前缀和与差分

前缀和也就是前n项或者前x项和的意思
//前缀和与差分是一个互逆的序列
Sn=A1+A2+···+An
S(2-5)=S5-S2 L=2 R=5
以下是一维前缀和java模板：

package 基础算法;
//模板之一--前缀和的一维与二维

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class 前缀和 {
    static int []sum = new int [10010];
    static int []s = new int [10010];
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        //一维前缀和
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int m = scan.nextInt();
        s[0]=0;
        for(int i=1;i<=n;i++) {
            sum[i] = scan.nextInt();
            s[i]=s[i-1]+sum[i];
        }
//      for(int i=1;i<=n;i++) {
//          System.out.print(sum[i]+"  ");
//      }
//      System.out.println();
//      for(int i=1;i<=n;i++) {
//          System.out.print(s[i]+"  ");
//      }
//      System.out.println();
        while(m-- > 0) {
            int l=scan.nextInt();
            int r=scan.nextInt();
            System.out.println(s[r]-s[l-1]);
        }
        //固定输入输出
//      int []nums= {0,2,3,5};
//      int []S=new int[nums.length];
//      S[0]=0;
//      for(int i=1;i<nums.length;i++) {
//          S[i]=S[i-1]+nums[i];
//      }
//      for(int i=0;i<S.length;i++) {
//          System.out.println(S[i]);
//      }
                
    }

}

二维前缀和：

package 基础算法;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 前缀和二维 {

    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        //加快输入，一次性读入到缓冲区，要读的时候再读
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        //读取一行
        String[] str1 = reader.readLine().split(" ");
        int n = Integer.parseInt(str1[0]);
        int m = Integer.parseInt(str1[1]);
        int q = Integer.parseInt(str1[2]);
        int [][]a = new int[n][m];
        int [][]s = new int[n+1][m+1];
        //将输入流放入a数组里
        for(int i=0;i<n;i++) {
            String[] str2 = reader.readLine().split(" ");
            for(int j=0;j<m;j++) {
                a[i][j]=Integer.parseInt(str2[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-1][j-1];
            }
        }
        for(int i=0;i<q;i++) {
            //读取一行
            String[] str3 = reader.readLine().split(" ");
            int x1 = Integer.parseInt(str3[0]);
            int y1 = Integer.parseInt(str3[1]);
            int x2 = Integer.parseInt(str3[2]);
            int y2 = Integer.parseInt(str3[3]);
            System.out.println(s[x2][y2]-s[x2][y1-1]-s[x1-1][y2]+s[x1-1][y1-1]);
        }
    }

}

前缀和可以应用在很多地方，以后会补充

差分

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int []a=new int[100010];
    static int []b=new int[100010];
    public static void insert(int l,int r,int c) {
        b[l]+=c;
        b[r+1]-=c;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        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++) {
            insert(i,i,a[i]);
        }
        while(m-->0) {
            int l=scan.nextInt();
            int r=scan.nextInt();
            int c=scan.nextInt();
            insert(l,r,c);
        }
        for(int i=1;i<=n;i++) {
            b[i]+=b[i-1];
        }
        for(int i=1;i<=n;i++) {
            System.out.print(b[i]+" ");
        }
    }

}

差分二维

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    static int [][]a = new int [1010][1010];
    static int [][]b = new int [1010][1010];
    public static void insert(int x1,int y1,int x2,int y2,int c) {
        b[x1][y1]+=c;
        b[x1][y2+1]-=c;
        b[x2+1][y1]-=c;
        b[x2+1][y2+1]+=c;
    }
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        //加快输入，一次性读入到缓冲区，要读的时候再读
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
        //读取一行
        String[] str1 = reader.readLine().split(" ");
        int n = Integer.parseInt(str1[0]);
        int m = Integer.parseInt(str1[1]);
        int q = Integer.parseInt(str1[2]);  
        //将输入流放入a数组里
        for(int i=1;i<=n;i++) {
            String[] str2 = reader.readLine().split(" ");
            for(int j=1;j<=m;j++) {
                a[i][j]=Integer.parseInt(str2[j-1]);
                insert(i,j,i,j,a[i][j]);
            }
        }
        while(q-->0) {
            String[] str3 = reader.readLine().split(" ");
            int x1 = Integer.parseInt(str3[0]);
            int y1 = Integer.parseInt(str3[1]);
            int x2 = Integer.parseInt(str3[2]);
            int y2 = Integer.parseInt(str3[3]);
            int c = Integer.parseInt(str3[4]);
            insert(x1,y1,x2,y2,c);
        }
        //所有值进行更新操作
        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];
            }
        }
        
      //最后结果输出
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                log.write(b[i][j]+" ");
            }
            log.write("\n");
        }
        reader.close();
        log.close();
        
    }

}