前缀与差分（java版）模板代码+题目

雨点打透心脏的1/2处 2024-03-31 13:15 18阅读 0赞

## 前言 ##

大家好，本文主要讲解的是一维，二维前缀与差分的使用，重点掌握公式，理解其用法。此外，小编水平有限，如果有错误的地方，还请多多指正。那么正文就开始啦 ![412201b62d80468180646d5e1d1c045f.png][]![abd4cff132cc45c18db5b1d7fe54c467.png][]![e76ce772bfee449c96e08e4250160a60.png][]

## ![759b8bdc5cf6409d9c00cc816c547e59.png][]目录![77a3507c16874b2197bc0a7d13bbae87.png][] ##

一维前缀和

如何求一维前缀和：

二维前缀和

如何求二位前缀和

一维差分

二维差分

练习题

习题1(一维前缀和)

练习题2（二维前缀和）

练习题3（一维差分）

总结

--------------------

## ![b356fad2af9d43dd8b298b3f34d76652.png][]一维前缀和 ##

**问题引入**

输入一个长度为n的整数序列。接下来再输入m个询问，每个询问输入一对l,r。对于每个询问，输出原序列中从第1个数到第r个数的和。

**定义**：S\[i\]为数组中1~i的总和，即s\[i\] = a\[1\] + a\[2\] + ... + a\[i\];（数组从1开始存值）

#### 如何求一维前缀和： ####

**核心代码**

for(int i = 1; i <= n; i++)
    {
        s[i] = s[i-1] + a[i]; //0~i-1的总和加上第i个数
    }

**注意**：**这里的i是从1开始，如果i是从0开始，s\[i\] = s\[i-1\] + a\[i-1\]（写起来比较方便）**

## ![0fdac8a190f149c4aa6c48aa429e4653.png][] ##

**完整代码**

import java.util.Scanner;
    
    public class 求前缀和
    {
        static int n; //数组长度
        static int m; //询问次数
        static int a[] = new int[100010]; //定义一个数组
        static int s[] = new int[100010]; //前缀和数组
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            n = sc.nextInt(); m = sc.nextInt();
            for(int i = 1; i <= n; i++)
            { //读入数组
                a[i] = sc.nextInt();
            }
            for (int i = 1; i <= n; i++) {
                s[i] = s[i - 1] + a[i]; //0~i的和
            }
            while(m-- != 0)
            {
                int l = sc.nextInt(), r = sc.nextInt();
                int ans = s[r] - s[l - 1];
                System.out.println(ans);
            }
        }
    }

## ![3c2fdecadcc343cd82a7cfe1703fa161.png][]二维前缀和 ##

**问题引入：**

输入一个n行m列的整数矩阵，再输入q个询问，每个询问包含四个整数`x1`,`y1`,`x2`,`y2`，表示一个子矩阵的左上角坐标和右下角坐标。

对于每个询问输出子矩阵中所有数的和。

定义：`s[i]][j]`为左上坐标为(1,1), 右下坐标为(i , j)的矩阵和（数组从(1,1)开始存储）

#### **如何求二位前缀和** ####

核心代码：

for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            s[i][j] = s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];
        }
    }

![47a484e73a0d4cad9f8f41f13181d919.png][]

![ac098ff211654a18aa05a125418711eb.png][]

![3e98f373648b415dbe5cfb634658d6b2.png][]

**完整代码**

import java.util.Scanner;
    
    public class 二维前缀和
    {
        static int n, m; //分别代表矩阵行数，列数
        static int[][] a = new int[1010][1010];//二维数组
        static int[][] s = new int[1010][1010];//二维前缀和数组
    
        public static void main(String[] args)
        {
            Scanner sc = new Scanner(System.in);
            n = sc.nextInt(); m = sc.nextInt();
            for(int i = 1; i <= n; i++) //输入二维矩阵
            {
                for(int j = 1; j <= m; j++)
                {
                    a[i][j] = sc.nextInt();
                }
            }
    
            //输出二维前缀和矩阵
            for(int i = 1; i <= n; i++)
            {
                for(int j = 1; j <=m; j++)
                {
                    s[i][j] = s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j]; //求二维数组前缀和公式
                    System.out.print(s[i][j] + " ");
                }
                System.out.println(); //换行输出
            }
        }
    }

还可以进行q次查询，在核心代码处加个while循环即可。

*  查询为 O(1)
 *  总时间复杂度：O(n\*m+q)

## ![0ad4cc95aaf141158c2474d4ab6e5d35.png][]一维差分 ##

**问题引入**

输入一个长度为n的整数序列。接下来输入m个操作，每个操作包含三个整数l,r,c，表示**将序列中\[l,r\]之间的每个数加上c。**

最后输出进行完所有操作后的序列。（1 <= n, m <= 100000）

**差分定义**：b\[i\] = a\[i\] - a\[i-1\], 即b\[i\]为第i个数与第i-1个数的差值（数组从1开始存）

![ab782e03081e48559924eddbd295bfef.png][]

特性：a\[i\] = b\[1\]+b\[2\]+ ... +b\[i\]（前缀和）

那对a数组中\[l,r\]之间的每个数加上c对b数组的影响是怎样的呢？

![6b2ac9f2ea7a4d3e82ac616adb222565.png][]

import java.util.Scanner;
    
    public class 一维差分
    {
        static int n; //数组长度
        static int m; //询问次数
        static int a[] = new int[100010]; //定义一个数组
        static int b[] = new int[100010]; //前缀和数组
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            n = sc.nextInt(); m = sc.nextInt();
            for(int i = 1; i <= n; i++)
            { //读入数组
                a[i] = sc.nextInt();
            }
            for (int i = 1; i <= n; i++) {
                b[i] = a[i] - a[i-1]; //求得的差分值赋给b数组
            }
            while(m-- != 0)
            {
                int l = sc.nextInt(),r = sc.nextInt(), c = sc.nextInt(); //在a数组l和r之间的每个数都加上c
                b[l] += c; b[r+1] -= c; // 对b数组的影响就是这样
                for(int i = 1; i <= n; i++)
                {
                    b[i] += b[i-1]; //求b数组前缀和，结果就是a[i]的值
                }
                for(int i = 1; i <= n; i++)
                {
                    System.out.print(b[i] + " "); //输出的结果就是增加后的a数组（l与r之间加上了c值）
                }
            }
        }
    }

*  询问O(1)
 *  时间复杂度：O(n+m)

## ![dab13c556dc743298a5523288c5b88b4.png][]二维差分 ##

**问题引入**

输入一个n行m列的整数矩阵，再输入q个操作，每个操作包含五个整数`x1`,`y1`,`x2`,`y2`,`c`, 其中`(x1,y1)`和`(x2,y2)`表示，一个子矩阵的左上角坐标和右下角坐标。每个操作都要将选中的子矩阵中的每个元素的值加上c。

最后将进行完所有操作后的矩阵输出（1 <= n, m<= 1000, 1 <=q <= 200000）

**定义**：`a[i][j]` = `a[1][1]`\+ `b[1][2]`\+ ... + `b[i][j]`((1,1)到(i,j)的矩阵和)（b为差分矩阵）

**注意：**根据一维差分的特性，二维差分也必定需要用到前缀和，但这里我们不能像一位那样先推出差分数组，而是利用修改操作得到差分矩阵。

![2ebe967c03c444e8b042221923360718.png][]

![c9b018294b4a461aad3a1ad36bc8c492.png][]

**初始差分矩阵**：b数组初始化为0，进行左上为(i,j), 右下为(i,j)，右下为(i,j) 矩阵添加`c[i][j]`的修改操作

for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            b[i][j] += c[i][j];
            b[i+1][j] -= c[i][j];
            b[i][j+1] -= c[i][j];
            b[i+1][j+1] += c[i][j];
        }
    }

**完整代码**

import java.util.Scanner;
    
    public class 二维差分 {
        static int n; //数组行数
        static int m; //询问列数
        static int a[][] = new int[1010][1010]; //定义二维数组
        static int b[][] = new int[1010][1010]; //二维差分数组
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            n = sc.nextInt(); m = sc.nextInt(); int c = sc.nextInt();
            for(int i = 1; i <= n; i++)
            { //读入数组
                for(int j = 1; j <= m; j++)
                {
                 a[i][j] = sc.nextInt();
                }
            }
            //初始化差分矩阵
            for(int i = 1; i <= n; i++)
            {
                for(int j = 1; j <= m; j++)
                {
                    b[i][j] += c;
                    b[i+1][j] -= c;
                    b[i][j+1] -= c;
                    b[i+1][j+1] += c;
                }
            }
            //求二维前缀和
            for(int i = 1; i <= n; i++)
            {
                for(int j = 1; j <=m; j++)
                {
                    b[i][j] = b[i][j-1]+b[i-1][j]-b[i-1][j-1]+a[i][j];
                }
            }
            for(int i = 1; i <= n; i++)
            {
                for(int j = 1; j <=m; j++)
                {
                    System.out.print(b[i][j] + " ");
                }
                System.out.println();
            }
        }
    }

## ![0d3f0a0aabec4d68b1724cdbd115e720.png][]练习题 ##

#### 习题1(一维前缀和) ####

**题目**

> ![60838acd60a149c59271506c12ab0caa.png][]
> 
> [蓝桥杯 2022 省赛 A 组 C 题][2022 _ A _ C]

**思路**

本题如果用常规方法，双重for循环遍历数组，时间复杂度为 O(n2)，如果运用些数学知识，例如前缀和，只用一个for循环即可完成求解，时间复杂度为 O(n)，运用一维前缀和，我们求出数组的和(sum)后，在遍历求和时，依次减去当前索引所指的数，再与这个被减的数相乘，就可以得到本题的答案。

**完整代码**

import java.util.Scanner;
    
    public class 求和 {
        public static void main(String[] args)
        {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt(); //数组长度
            Long[] a = new Long[n]; //定义一个数组
            Long sum = 0l; //总和初始化为0
            for (int i = 0; i < a.length; i++)
            {
                a[i] = sc.nextLong();//读入数组
                sum += a[i]; //求前缀和
            }
            Long res = 0l; //存放答案
            for(int i = 0; i < a.length; i++)
            {
                sum -= a[i]; 
                res += sum*a[i]; //求总和
            }
            System.out.println(res);
            sc.close();
        }
    }

#### **练习题2（二维前缀和）** ####

> **![a0e10d7e2ae74671a159c40e998e21b2.png][]**
> 
> [激光炸弹][Link 1]

**思路**

这是一道二维前缀和的经典题型，题目要求边上的不能算上，所以我们处理边长-R的前缀和即可。最终求出最优爆炸范围，我们先求出前缀和，也就是总的范围，然后减去R\*R的范围，也就是不能爆炸的范围，就得到了被爆炸的范围，具体画图一下比较好理解。

import java.util.Scanner;
    
    public class 激光炸弹
    {
        static int n,R; //分别表示n行(n个目标)，边长为R的正方形
        static int[][] a = new int[5010][5010]; //原矩阵
        static int[][] s = new int[5010][5010]; //二维前缀和矩阵
    
        public static void main(String[] args)
        {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt(),R = sc.nextInt();
            for(int i = 1; i <= n; i++)
            {
                int x = sc.nextInt(), y = sc.nextInt(), v = sc.nextInt();
                a[x+1][y+1] += v;//注意：数组会越界，所以坐标x，y都要加1；这道题目坐标从0开始，但我们从1开始处理
            }
            //求前缀和
            for(int i = 1; i <= 5001; i++)
            {
                for(int j = 1; j <= 5001; j++)
                {
                    s[i][j] = s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];
                }
            }
            R = Math.min(R,5001);
            long max = 0;
            for(int i = R; i <= 5001; i++)
            {
                for(int j = R; j <= 5001; j++)
                {
                    max=Math.max(max,s[i][j]-s[i-R][j]-s[i][j-R]+s[i-R][j-R]);
                }
            }
            System.out.println(max);
        }
    }

#### 练习题3（一维差分） ####

> ![63634ed6572b4984be6985bb18b8b832.png][]
> 
> [积木大赛][Link 2]

**思路**

这道题思路还是比较简单的，简单画个草图就能差不多看出来，要在连续区间内建造积木，就想到了差分，如果下一栋积木比上一栋高，差分出来为正，就是我们需要建造的，反之，如果下一栋积木比上一栋积木矮，为负数，这个区间就不是连续的，也证明不需要我们建造哦。

**代码实现**

import java.util.Scanner;
    
    public class 积木大赛
    {
        public static void main(String[] args)
        {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int a[] = new int[100010];
            int b[] = new int[100010];
            for (int i = 1; i <= n; i++)
            {
                a[i] = sc.nextInt();
            }
            for(int i = 1; i <= n; i++)
            {
                b[i] = a[i] - a[i-1];
            }
            int ans = 0;
            for(int i = 1; i <= n; i++)
            {
                if(b[i] > 0) ans += b[i]; //注意：这里要约束b[i]>0
            }
            System.out.println(ans);
        }
    }

--------------------

好了，练习题目就到这里吧，二维差分就不练习了，等小编达到了一定高度再细发...**如果本文对你有帮助，就给个一键三连吧，也可以收藏起来观看。**![ab049de7fbb64ef2b626d96d5325024f.png][]

## 总结 ##

本文一共讲解了一维前缀和，二维前缀和，一维差分，二维差分。主要需要记住使用的公式和分析在什么场景下使用哪一个。需要详细掌握还得多多做题！大家一起加油吧！![f71eae94292d4a24be1636b234e5b662.png][]

--------------------

[412201b62d80468180646d5e1d1c045f.png]: https://img-blog.csdnimg.cn/412201b62d80468180646d5e1d1c045f.png
[abd4cff132cc45c18db5b1d7fe54c467.png]: https://img-blog.csdnimg.cn/abd4cff132cc45c18db5b1d7fe54c467.png
[e76ce772bfee449c96e08e4250160a60.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/9ef99537a5f447e0ab04c02c013d1115.png
[759b8bdc5cf6409d9c00cc816c547e59.png]: https://img-blog.csdnimg.cn/759b8bdc5cf6409d9c00cc816c547e59.png
[77a3507c16874b2197bc0a7d13bbae87.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/4eae3de1b65f4229b631fe8977d9b7c2.png
[b356fad2af9d43dd8b298b3f34d76652.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/0897a5800401403db0553224ecccfa34.png
[0fdac8a190f149c4aa6c48aa429e4653.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/43009caaf1634d2f8d572e1f2d7e086f.png
[3c2fdecadcc343cd82a7cfe1703fa161.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/0b189948b13d46c4bf2e936d69d61afb.png
[47a484e73a0d4cad9f8f41f13181d919.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/1e9e446e684345989081d91e6089e302.png
[ac098ff211654a18aa05a125418711eb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/dad52e1b25684860a1d72cb96c774504.png
[3e98f373648b415dbe5cfb634658d6b2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/f572348d578c40feadf7b2cdc58f4315.png
[0ad4cc95aaf141158c2474d4ab6e5d35.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/b70cd3a51bc24fa4be41f592bbf9c7bb.png
[ab782e03081e48559924eddbd295bfef.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/fa994fc29a6343deaa8e24d1b5b8ce06.png
[6b2ac9f2ea7a4d3e82ac616adb222565.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/33a5b82b85b9412ca65bbcd39d6d06eb.png
[dab13c556dc743298a5523288c5b88b4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/fe48af8d1f5d47c18f546662bef3b032.png
[2ebe967c03c444e8b042221923360718.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/d5ff7c80b9cc4a7c8d272597eb89d821.png
[c9b018294b4a461aad3a1ad36bc8c492.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/d3914c6f1dd54d8e8f514de31573aa2e.png
[0d3f0a0aabec4d68b1724cdbd115e720.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/f8cea1456f52498299b9477993fa1316.png
[60838acd60a149c59271506c12ab0caa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/99bf9237f2e44c07a134c520de2ce3f0.png
[2022 _ A _ C]: https://www.luogu.com.cn/problem/P8772
[a0e10d7e2ae74671a159c40e998e21b2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/8bcf0a6d82c44c0498d5caea1779670d.png
[Link 1]: https://ac.nowcoder.com/acm/problem/20032?&headNav=acm
[63634ed6572b4984be6985bb18b8b832.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/f1ffedde397241a189880d0e37a835d6.png
[Link 2]: https://ac.nowcoder.com/acm/problem/16534
[ab049de7fbb64ef2b626d96d5325024f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/9c31dbac24b04abab8e28cda9a1e3aa5.png
[f71eae94292d4a24be1636b234e5b662.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/1d1eb67615ef47a586d048128f63b947.png