数据结构--前缀和与差分

2023-11-19

字数统计: 888字 | 阅读时长≈ 4分

前缀和：适用于数组不经常变化，但是经常需要查询某一个区间的区间和的情况，前缀和数组每次查询区间和时间复杂度为O(1)。普通数组每次查询区间和时间复杂度为O(n)。

作用：查询区间和
一维前缀和：sum[i]表示从0到i元素的累加和，sum[i]=sum[i-1]+arr[i]
二维前缀和：sum[i][j]表示从(0,0)到(i,j)的矩阵的和，sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+arr[i][j]

一维前缀和：

avatar

/**
 * 一维前缀和
 * @author zzr
 * @create 2023-11-18-15:37
 */
public class Prefix {
    int[] sum;

    public Prefix(int[] arr) {
        int n=arr.length;
        sum=new int[n];
        sum[0]=arr[0];
        for (int i = 1; i < n; i++) {
            sum[i]=sum[i-1]+arr[i];//前缀和公式
        }
    }

    /**
     * 查询区间和
     */
    public int getSum(int left,int right){
        return left<1?sum[right]:sum[right]-sum[left-1];
    }
}

代码简化：从1开始放

avatar

/**
 * 前缀和
 * @author zzr
 * @create 2023-11-18-15:37
 */
public class Prefix {
    int[] sum;

    public Prefix(int[] arr) {
        int n=arr.length;
        sum=new int[n+1];
        for (int i = 0; i < n; i++) {
            sum[i+1]=sum[i]+arr[i];//前缀和公式
        }
    }

    /**
     * 查询区间和
     */
    public int getSum(int left,int right){
        return sum[right+1]-sum[left];
    }
}

二维前缀和：

avatar

差分：适用于对数组进行多次区间修改后,最终确定原数组值的情况，差分数组每次区间修改时间复杂度为O(1)。普通数组每次修改区间和时间复杂度为O(n)。

作用：区间修改

差分与前缀和互为逆运算：

avatar

一维差分性质：对原数组进行从[left，right]区间内每个数增加val的值,只需对差分数组进行diff[left]+val和diff[right+1]-val，再通过对差分数组进行一维前缀和便可得修改后的原数组

avatar

二维差分性质：对原数组进行从[a，b]到[c,d]矩阵内每个数增加v的值,只需对差分数组进行diff[a][b]+v、diff[a][d+1]-v、diff[c+1][b]-v、diff[c+1][d+1]+v,再通过对差分数组进行二维前缀和便可得修改后的原数组

avatar

一维差分应用：lettcode 1109 https://leetcode.cn/problems/corporate-flight-bookings/

这里有 n 个航班，它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。

请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

示例 1：
输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]

解释：
航班编号        1   2   3   4   5
预订记录 1 ：   10  10
预订记录 2 ：       20  20
预订记录 3 ：       25  25  25  25
总座位数：      10  55  45  25  25
因此，answer = [10,55,45,25,25]

示例 2：
输入：bookings = [[1,2,10],[2,2,15]], n = 2
输出：[10,25]

解释：
航班编号        1   2
预订记录 1 ：   10  10
预订记录 2 ：       15
总座位数：      10  25
因此，answer = [10,25]
 
提示：
1 <= n <= 2 * 104
1 <= bookings.length <= 2 * 104
bookings[i].length == 3
1 <= firsti <= lasti <= n
1 <= seatsi <= 104

public int[] corpFlightBookings(int[][] bookings, int n) {
    int[] diff=new int[n];
    for (int[] booking : bookings) {
        int left = booking[0];
        int right = booking[1];
        int val = booking[2];
        diff[left-1]+=val;
        if (right<n) {
            diff[right] -= val;
        }
    }
    for (int i = 1; i < n; i++) {
        diff[i]+=diff[i-1];
    }
    return diff;
}

本文作者： zzr
本文链接： http://zzruei.github.io/2023/11d8b27ba1.html
版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！