【算法和数据结构】前缀和-创新互联

1.概念定义 1）部分和

部分和就是给定一个一个数组arr,求其中某一段连续子数组[l,r]的和。通常的做法是遍历l到r之间的元素相加，这样的作法最坏时间复杂度可以达到O(n),如果有m次访问时间复杂度达到了O(mn)。基于对上述问题的优化，我们引入前缀和的概念。

2）前缀和

我们可以声明一个数组sum，来记录数组前i项的和，可以得出递推公式sum[i]=sum[i-1]+arr[i]。有了递推公式，我们还要考虑边界值，即sum[0]的值，由于此时sum[0]=a[0]，可得出sum[-1]=0。由于代码中下标不能为-1，只要做一次i的判断就可以了。

3）通过前缀和计算部分和

有了sum数组之后，我们就可以利用差分法，用sum[r]-sum[l-1]即可求出[l,r]区间内所有元素的和，每一次计算时间复杂度都是O(1)。

2.算法详解 1)前缀和

例：给定一个整数数组num，请计算数组的中心下标。如果数组有多个中心下标，应该返回最靠近左边的那一个。如果数组不存在中心下标，返回-1。中心下标是数组的一个下标，其左侧所有元素加起来的和等于右侧所有元素加起来的和。

成都创新互联长期为1000+客户提供的网站建设服务，团队从业经验10年，关注不同地域、不同群体，并针对不同对象提供差异化的产品和服务；打造开放共赢平台，与合作伙伴共同营造健康的互联网生态环境。为寿县企业提供专业的网站建设、成都网站建设，寿县网站改版等技术服务。拥有10多年丰富建站经验和众多成功案例,为您定制开发。

思想：从左往右枚举数组中的元素，计算左侧元素和与右侧元素和，若两者相等则直接返回下标。每次计算时间复杂度O(1)，总过程为O(n)。代码实现如下。

public int pivotIndex(int[] arr){int size = arr.length;
    int[] sum = new int[size];
    //计算前缀和
    for(int i=0;isum[i] = arr[i];
        if(i>0){sum[i] += sum[i-1];
        }
    }
    //判断边界值0
    if(sum[0] == sum[size-1]){return 0;
    }
    //遍历数组分别计算每一个元素的左侧和和右侧和
    for(int i=1;iif(sum[i-1] == sum[size-1]-sum[i]){return i;
        }
    }
    //找不到中心坐标返回-1
    return -1;
}

2）前缀积

例：给定一个整数数组num，返回输出数组output，其中output[i]为num中除num[i]外所有数的乘积。

思想：前缀和的变种，求和改为求积即可，同理的还有前缀异或和，即sum[i]=sum[i-1]^a[i]。此题的代码实现如下。

public int[] productExceptSelf(int[] arr){int size = arr.length;
    int[] pre = new int[size];
    //计算前缀积
    for(int i=0;ipre[i] = arr[i];
        if(i>0){pre[i] *= pre[i-1];
        }
    }
    //为了方便后续计算，同时计算出后缀积
    int[] post = new int[size];
    for(int i=size-1;i>=0;i--){post[i] = arr[i];
        if(ipost[i] *= post[i+1];
        }
    }
    int[] result = new int[size];
    //为了计算方便，这里取i-1的前缀积乘i+1的后缀积作为结果
    for(int i=0;iif(i==0){result[i] = post[i+1];
        }else if(i==size-1){result[i] = pre[i-1];
        }else{result[i] = pre[i-1]*post[i+1];
        }
    }
    return result;
}

3.前缀和统计 1）问题引入

给定一个整数数组arr，其初始元素都为0。然后选择一个区间[1,5]，给其中每个元素加3；在选择一个区间[3,6]，给其中每个元素加2。求此时arr中每个元素的值是多少。

2）朴素算法

假设数组长度为n，总共经过m次累加操作，如果每次累加都需要遍历区间内所有元素的话，最坏情况时间复杂度为O(mn)。

3）优化算法

当在数组arr的[l,r]区间上累加一个数x时，可以在l位置加x，再在r+1的位置减x，再求前缀和，就是我们要的结果。此时每次累加操作时间复杂度为O(1)，整个过程为O(n)。

4.前缀和统计例题

例：这里有n个航班，它们分别从1到n进行编号。有一份航班预定表bookings，表中第i条记录为bookings[i]=[firsti,lasti,seatsi]，意味着在从firsti到lasti的每个航班，都预定了seatsi个座位。请你返回一个长度为n的数组，里面的元素是每个航班预定的座位总数。

思想：对每个区间[firsti,lasti]，我们在firsti的位置加seatsi，在lasti+1的位置减seatsi，最后统计前缀和就是答案。代码实现如下。

public int[] cropFlightBookings(int[][] bookings,int n){//初始化一个所有元素都是0的数组
    int[] sum = new int[n+1];
    //用O(1)的方式操作数组，使其满足在区间[firsti,lasti]上增加seatsi
    for(int i=0;iint first = bookings[i][0];
        int last = bookings[i][1];
        int seats = bookings[i][2];
        sum[first] += seats;
        sum[last+1] -= seats;
    }
    int[] res = new int[n];
    //对数组sum求前缀和即可求出结果
    for(int i=1;ires[i-1] = sum[i];
        if(i>1){res[i-1] += res[i-2];
        }
    }
    return res;
}

5.差分数组

上文所讲的前缀和统计用的例子都是初始为0的数组，当数组初始元素不为0则无法进行前缀和统计的操作，这种情况下，我们需要自己创造一个数组d，使它的前缀和sum[i]=arr[i]。根据前缀和的定义，我们可以递推出该数组中的元素d[i]=arr[i]-arr[i-1]。数组d就叫做arr的差分数组。在数组d上即可进行上述的前缀和统计操作。

习题

1894. 找到需要补充粉笔的学生编号

2256. 最小平均差

1737. 满足三条件之一需改变的最少字符数

2055. 蜡烛之间的盘子

文章内容为英雄哥算法星球的个人学习总结，B站英雄哥直播间：https://live.bilibili.com/24513717，每日凌晨5点到8点直播刷题。
注：本文章搬运自个人博客。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网站标题：【算法和数据结构】前缀和-创新互联
本文URL：http://bjjierui.cn/article/dcdgeo.html