前缀和算法题1

/**
     * https://www.nowcoder.com/practice/acead2f4c28c401889915da98ecdc6bf
     *
     * 本题采用前缀和的思想（用来快速的得到数组某一段区间里的值的和）
     * 首先录入数组arr
     * 创建一个dp数组用来存放数组的前缀和
     * dp[i]就表示arr数组[0,i]里面的值的和
     * dp[i]里面的i从一开始计数
     * 使用dp[i]=dp[i-1]+arr[i]接口快速的到数据
     * 需要算出arr数组[l,r]区间的值
     * 就可以使用dp[r]-dp[l-1]的值来输出
     * 此时需要注意，dp[i]的i需要从1开始，原因时因为当计算arr数组中[0,2]的值时
     * 从0开始的画会造成dp[2]-dp[-1]造成数据的越界访问，因此将dp[0]的值置成0即可不影响数据
     * */
    public static void hanShu1(){
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int q= in.nextInt();
        int[] arr=new int[n+1];
        long[] dp=new long[n+1];
        for (int i = 1; i <= n; i++) {
            arr[i]=in.nextInt();
        }
        for (int i = 1; i <=n; i++) {
            dp[i]=dp[i-1]+arr[i];
        }
        while (q>0){
            int l=in.nextInt();
            int r=in.nextInt();
            System.out.println(dp[r]-dp[l-1]);
            q--;
        }
    }

/**
     * https://www.nowcoder.com/practice/99eb8040d116414ea3296467ce81cbbc
     * 详情看图
     * */
    public static void hanShu2(){
        Scanner in = new Scanner(System.in);
        int n=in.nextInt();
        int m=in.nextInt();
        int q=in.nextInt();
        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]=in.nextInt();
            }
        }
        long[][] dp=new long[n+1][m+1];
        dp[0][0]=0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+arr[i][j];
            }
        }
        while (q>0){
            int x1=in.nextInt();
            int y1=in.nextInt();
            int x2=in.nextInt();
            int y2=in.nextInt();
            long result=dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1];
            System.out.println(result);
            q--;
        }
    }

/**
     * https://leetcode.cn/problems/find-pivot-index/
     * 见图
     * */
    public static void hanShu3(int[] nums){
        int n=nums.length;
        int[] f=new int[n];
        int[] g=new int[n];
        f[0]=g[n-1]=0;
        for (int i = 1; i < n; i++) {
            f[i]=f[i-1]+nums[i-1];
        }
        for(int j=n-2;j>=0;j--){
            g[j]=g[j+1]+nums[j+1];
        }
        for (int i = 0; i < n; i++) {
            if (f[i]==g[i]){
                System.out.println("ok->"+i);
                return;
            }
        }
    }

/**
     * https://leetcode.cn/problems/product-of-array-except-self/
     * 见图
     * */
    public static void hanShu4(int[] nums){
        int n=nums.length;
        long[] f=new long[n];
        long[] g=new long[n];
        long[] arr=new long[n];
        f[0]=g[n-1]=1;
        for (int i = 1; i < n; i++) {
            f[i]=f[i-1]*nums[i-1];
        }
        for(int j=n-2;j>=0;j--){
            g[j]=g[j+1]*nums[j+1];
        }
        for (int i = 0; i < n; i++) {
            arr[i]=f[i]*g[i];
        }
    }