前缀和与差分算法

前缀和算法(prefix sum)

前缀和是一种简单的有效的优化算法，能把计算复杂度为O(n)的区间计算优化为O(1)的端点计算

前缀和的概念

一个长度为n的数组a[1]_{a[n]，前缀和sum[i]等于a[1]}a[i]的和：

sum[i]=a[1]+a[2]+...+a[i]

利用递推，可以在O(n)时间内求得所有前缀和：

sum[i]=sum[i-1]+a[i]

如果预计算出前缀和，就能利用它快速计算出数组中任意一个区间a[i]~a[j]的和，即：

a[i]+a[i+1]+...+a[j-1]+a[j]=sum[j]-sum[j-1]

上式说明，复杂度为O(n)的区间求和计算，优化到了O(1)的前缀和计算

前缀和例题

如果建模时发现有区间求和操作，可以考虑使用前缀和优化

例一 0求和 - 蓝桥云课 (lanqiao.cn)

将给定的计算式子变换为：

\[ S = (a_1 + a_2 + \ldots + a_{n-1}) \times a_n + (a_1 + a_2 + \ldots + a_{n-2}) \times a_{n-1} + (a_1 + a_2 + ldots + a_{n-3}) \times a_{n-2} + \ldots + (a_1 + a_2) \times a_3 + a_1 \times a_2 \]

其中括号内的部分是前缀和 \[ sum[i] = a_1 + a_2 + \ldots + a_i \] ，把上式改写为：

\[ S = sum[n - 1] \times a_n + sum[n - 2] \times a_{n-1} + sum[n - 3] \times a_{n-2} + \ldots + sum[2] \times a_3 + sum[1] times a_2 \]

式子中用到的前缀和 sum[1] ~ sum[n-1]，用递推公式 sum[i] = sum[i-1] + a[i]做一次for循环就能全部提前计算出来。

# 一个长度为n的数组a[1]~a[n]，前缀和sum[i]等于a[1]~a[i]的和：
# sum[i]=a[1]+a[2]+...+a[i]
# 利用递推，可以在O(n)时间内求得所有前缀和：
# sum[i]=sum[i-1]+a[i]
# 如果预计算出前缀和，就能利用它快速计算出数组中任意一个区间a[i]~a[j]的和，即：
# a[i]+a[i+1]+...+a[j-1]+a[j]=sum[j]-sum[j-1]
# 上式说明，复杂度为O(n)的区间求和计算，优化到了O(1)的前缀和计算

n = int(input())
a = [0]+[int(i) for i in input().split()]    #读入a[1]~a[n]。a[0]不用
sum = [0] * (n+1) #定义前缀和-->[0, 0, 0, 0, 0, 0, 0]
sum[1] = 0
for i in range(1,n):
    sum[i] = a[i]+sum[i-1]  #预计算前缀和sum[1]~sum[n-1]
s=0
for i in range(1,n):
    s += sum[i]*a[i+1]      #计算和s
print(s)

例二 0可获得的最小取值 - 蓝桥云课 (lanqiao.cn)

第一步肯定是排序，例如从小到大排序，然后再进行两种操作。操作（1）在a[]的尾部选一个数，操作（2）在a[]的头部选2个数。

容易想到一种简单方法：每次在操作（1）和操作（2）中选较小的值。这是贪心法的思路。但是贪心法对吗？分析之后发现贪心法是错误的，例如{3, 1, 1, 1, 1, 1, 1}，做k=3次操作，每次都按贪心法，做3次操作（2），结果是6。但是正确答案是做3次操作（1），结果是5。

回头重新考虑所有可能的情况。设操作（2）做p次，操作（1）做k-p次，求和：

\[ \sum_{i=1}^{2p} a_i + \sum_{i=n+p-k+1}^{n} a_i \]

为了找最小的和，需要把所有的p都试一遍。如果直接按上面的公式计算，那么验证一个p的计算量是O(n)的，验证所有的p，1≤p≤k，总计算量O(kn)，超时。

容易发现公式的两个部分就是前缀和，分别等于sum[2p]、sum[n] - sum[n+p-k]。如果提前算出前缀和sum[]，那么验证一个p的时间是O(1)的，验证所有p的总计算量是O(n)的。

n, k = map(int, input().split())
b = list(map(int, input().split()))
a=[0] + sorted(b)       # a[0]不用，从a[1]开始
s = [0] * (n+1)
for i in range(1, n+1):  
    s[i] = s[i-1] + a[i]
ans = 10**18
for p in range(1, k+1):
    ans = min(s[n] - s[n+p-k] + s[2*p], ans)
print(ans)

例三 二维前缀和

  前面的例子都是一位数组上的前缀和，下面介绍二维数组上的前缀和。 例题：领地选择   概况题意：在n×m 的矩形中找一个边长为c的正方形，把正方形内所有坐标点的值相加，使价值最大。   本题是二维前缀和的直接应用。   一维前缀和定义在一维数组a[]上：sum[i] = a[1] + a[2] + … + a[i]   把一维数组a[]看成一条直线上的坐标，前缀和就是所有坐标值的和。

  二维前缀和是一维前缀和的推广。设二维数组a[][]有1_n行，1m列，二维前缀和：     sum[i][j] = a[1][1]+a[1][2]+a[1][3]+…+a[1][j]         + a[2][1]+a[2][2]+a[2][3]+…+a[2][j]         + …         + a[i][1]+a[i][2]+a[i][3]+…+a[i][j]   把a[i][j]的(i,j)看成二维平面的坐标，那么sum[i][j]就是左下角坐标(1,1)和右上角坐标(i,j)围成的方形中所有坐标点的和。

  二维前缀和sum[][]存在以下递推关系：   sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]   根据这个递推关系，用两种for循环可以算出sum[][]。   对照上图理解这个公式，sum[i-1][j]是坐标(1,1) ~ (i-1, j)内所有的点，sum[i][j-1]是(1,1) ~ (i, j-1)内所有的点，两者相加，其中sum[i-1][j-1]被加了两次，所以要减去一次。

n, m , c = map(int, input().split())
a = []
a.append([0]*(m+1))
for i in range(0, n):
    a.append([int(k) for k in input().split()])
    a[i+1].insert(0, 0)
for i in range(1, n+1):
    for j in range(1, m+1):
        a[i][j] = a[i][j] + a[i-1][j] + a[i][j-1] - a[i-1][j-1]
Max = float('-inf')
for i in range(1, n+2-c):
    for j in range(1, m+2-c):
        ans = a[i+c-1][j+c-1] - a[i+c-1][j-1] - a[i-1][j+c-1] + a[i-1][j-1]
        if ans > Max:
            Max = ans
            x = i
            y = j
print(x, y)

差分算法

前缀和的主要应用是差分：差分是前缀和的逆运算。   与一维数组a[]对应的差分数组d[]的定义：     d[k]=a[k]-a[k-1]   即原数组a[]的相邻元素的差。根据d[]的定义，可以推出：     a[k]=d[1]+d[2]+…+d[k]   即a[]是d[]的前缀和，所以“差分是前缀和的逆运算”。   为方便理解，把每个a[]看成直线上的坐标。每个d[]看成直线上的小线段，它的两端是相邻的a[]。这些小线段相加，就得到了从起点开始的长线段a[]。   差分是一种处理数据的巧妙而简单的方法，它应用于区间的修改和询问问题。把给定的数据元素集A分成很多区间，对这些区间做很多次操作，每次操作是对某个区间内的所有元素做相同的加减操作，若一个个地修改这个区间内的每个元素，非常耗时。引入“差分数组”，当修改某个区间时，只需要修改这个区间的“端点”，就能记录整个区间的修改