一维前缀和

前缀合数组表示： 

1
2
3
4
5
a=[]
ls=[]
ls[0]=a[0]
for i in range(1,n):
    ls[i]=ls[i-1]+a[i]
pre_sum[a]表示从原数组的第一个数加到下标为a的数之和。

在创建前缀和数组以后，如果要查询原数组在区间[a,b]上的元素和，只需要使用公式pre_sum[b]-pre_sum[a-1]即可。

1
2
3
4
5
6
pre_sum=[n]
def get_sum(l,r):
    if(l != 0):
        return pre_sum[r]-pre_sum[l-1]
    else:
        return pre_sum[r]

一维差分

差分数组构造： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 给定的数组 a
a = [1, 3, 3, 5, 10]
 
 
# 1. 写出差分数组
a=[1,2,3,4,5,6,7]
diff=[]

def get_diff_array(a):
    n = len(a)
    diff = [a[0]]  # 差分数组的第一个元素就是原数组的第一个元素
    for i in range(1, n):
        diff.append(a[i] - a[i - 1])  # 相邻元素两两作差
    return diff

若diff[3]+=2,则a[3]后面所有数都+2, 所以若只想在[l,r]区间+2，则需补充diff[r+1]-=2 
1
2
diff[l]+=2
diff[r+1]-=2
之后再前缀和还原数组

二维前缀和

前缀和的构造：对于a[i][j]的前缀和，等于左上的值+左前缀和+上前缀和-左上前缀和 构造二维前缀和数组时，可以现在最外层加一圈0。 

1
2
3
4
5
6
7
8
9

n, m = len(grid), len(grid[0])  # 得到行数和列数
 s = [[0] * (m + 1) for _ in range(n + 1)]  # 初始化二维前缀和数组

for i in range(1, n + 1):
    for j in range(1, m + 1):
        s[i][j] = (
            s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + grid[i - 1][j - 1]
        )
得到前缀和： 
1
2
def get_sum(x1, y1, x2, y2):
    return s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]
# 二维差分

二维差分处理的部分右下。一般思路为先把差分矩阵写出来，再将其前缀和并作用于原矩阵。

1
2
3
4
5
6
7
8
9
10
diff=[[0]*(n-1 for _ in range(n+1))]#防越界
diff[x1][y1]+=1
diff[x2+1][y1]-=1
diff[x1][y2+1]-=1
diff[x2+1][y2+1]+=1

for i in range(1, n + 1):  # 对差分数组做二维前缀和还原为原数组
    for j in range(1, n + 1):
        a[i][j] = a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1] + diff[i - 1][j - 1]
        #前缀和复原