AcWing 795. 前缀和理解_Java

AcWing 795. 前缀和理解_Java 原题链接简单

作者：

zning , 2019-09-20 12:28:55 , 所有人可见 , 阅读 9075

76

56

前缀和

什么是前缀和

原数组: a[1], a[2], a[3], a[4], a[5], …, a[n]
前缀和 Si为数组的前 i项和
前缀和: S[i] = a[1] + a[2] + a[3] + … + a[i]

注意: 前缀和的下标一定要从 1开始, 避免进行下标的转换

s[0] = 0
s[1] = a[1]
s[2] = a[1] + a[2]

前缀和的作用

快速求出元素组中某段区间的和

一维数组求解前缀和(Si)

for循环求出每个S[i] (将 S[0] 定义为 0, 避免下标的转换)
求 [l, r]中的和, 即为 S[r] - S[l-1]

题目: 795

代码

import java.util.*;

public class Main {
    private static int N = 100010;  // 定义数组大小, 防止越界

    public static void main(String[] args) {
        // 初始化输入值
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] arr = new int[N];
        // 注意这里是从 1开始的
        for (int i = 1; i <= n; i++)     
            arr[i] = in.nextInt();

        // s[i]代表 arr的前 i项和
        int s[] = new int[N];   
        s[0] = 0;   
        // 计算出 s[i]
        for (int i = 1; i <= n; i++)
            s[i] = s[i - 1] + arr[i];     // 注意运算方式

        // 循环输出
        while (m-- > 0) {
              int l = in.nextInt();
              int r = in.nextInt();
              System.out.println(s[r] - s[l - 1]);  // 关键
        }
    }
}

二维数组求解前缀项和

求解s[i][j]

如图

求S[i][j].png

求解前缀项和

如图

前缀和.png

题目 796

代码

import java.util.*;

public class Main {

    public static void main(String[] args) {
        // 输入值进行初始化
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int q = in.nextInt();
        // 初始化 arr
        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();
//         输出查看 arr
//        for (int i = 1; i <= n; i++) {
//            for (int j = 1; j <= m; j++)
//                System.out.print(arr[i][j] + "  ");
//        }

        // 求解 s[i][j]
        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];

        // 循环输出
        while (q-- > 0) {
            // 定位获取区间大小
            int x1 = in.nextInt();
            int y1 = in.nextInt();
            int x2 = in.nextInt();
            int y2 = in.nextInt();

            // 计算, 结合图来理解
            int res = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
            System.out.println(res);
        }
    }
}

14 评论

sjiss 2021-11-25 11:00

这图画的，真清晰呀

笨死了 11天前

学习总结了一、二维前缀和差分，希望对你有帮助~
https://blog.csdn.net/m0_74215326/article/details/129620912?spm=1001.2014.3001.5502

Carrot_8 2个月前

想问一下佬为什么是x1-1,这是啥意思

y差c 1个月前

二维数组x表示行，y表示列，x1代表左上角的起始点。但是得从x1的上一行开始算，不然，x1的那行的点都要被减去了，所以要从x-1开始哦

y差c 1个月前

说错了，是i表示行，j表示列；x,y分别表示点的坐标

2323301456 4个月前

大佬,为啥后面循环写m–>0可以运行,我写的是m>0,然后在循环的最后写的m–不能运行呢,难以理解

应该可以考上的 10个月前

佬，格子图可以拿走不？看了之后醍醐灌顶！

菜鸡栩 2022-03-30 18:14

这图拿走了大佬

柠檬味的胡萝卜 2021-09-06 10:43

大佬，一维前缀求和那，你防止数组索引越界，定义的容量太大，有点浪费，我定义的n+1，也AC了
import java.util.*;

public class Main{

public static void main(String[] args)
{
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int m=sc.nextInt();
    //防止循环时 索引越界
    int[] nums=new int[n+1];
    for(int i=1;i<=n;i++)
    {
        nums[i]=sc.nextInt();
    }
    int[] sums=new int[n+1];
    sums[0]=0;
    for(int i=1;i<=n;i++)
    {
        sums[i]=sums[i-1]+nums[i];
    }
    while(m-->0)
    {
        int l=sc.nextInt();
        int r=sc.nextInt();
        System.out.println(sums[r]-sums[l-1]);
    }
}

}

vieper0714 6个月前

我觉得sums[0] = 0比较多余,然后nums没必要开n+1

vieper0714 6个月前

这是我写的

import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] a = new int[n];
        int[] s = new int[n + 1];
        for (int i = 0 ; i < a.length ; i ++)
            a[i] = sc.nextInt();
        for (int i = 1; i < s.length ; i++){
            s[i] = s[i - 1] + a[i - 1];
        }
        while(m-- > 0){
            int l = sc.nextInt(),r = sc.nextInt();
            System.out.println(s[r] - s[l - 1]);
        }


    }

}