0X00 一維前綴和
n, m = map(int, input().split())
nums = list(map(int, input().split()))
sums = [0] * (n+1)
for i in range(1, n+1):
sums[i] = sums[i-1] + nums[i-1]
for _ in range(m):
n1, n2 = map(int, input().split())
print(sums[n2] - sums[n1-1])
0X01 二維前綴和
n, m = map(int, input().split())
nums = list(map(int, input().split()))
sums = [0] * (n+1)
for i in range(1, n+1):
sums[i] = sums[i-1] + nums[i-1]
for _ in range(m):
n1, n2 = map(int, input().split())
print(sums[n2] - sums[n1-1])
0X02 一維差分
一維差分推導(dǎo)：
假設(shè)我們有數(shù)組 a 現(xiàn)在構(gòu)造一個(gè)數(shù)組 b 使得：
那么 b 的前 n 項(xiàng)和就是
并且如果我們向
增加一個(gè)數(shù) c 那么再求
到
的時(shí)候都會加上一個(gè) c。因此我們完成了在
的時(shí)間給一段數(shù)加上某一個(gè)數(shù)
現(xiàn)在我們來寫它的模板：
差分只有一個(gè)操作 add，就是給一段區(qū)間加上一個(gè)值并徘，
def add(l, r, v):
b[r+1] -= v
b[l] += v
n, q = map(int, input().split())
a = list(map(int, input().split()))
b = [0] * (n+1)
def add(l, r, v):
b[r+1] -= v
b[l] += v
for i, v in enumerate(a):
add(i, i, v)
# print(b)
while q > 0:
q -= 1
l, r, v = map(int, input().split())
add(l-1, r-1, v)
0X03 二維差分
構(gòu)造一個(gè)二維數(shù)組 b 使得 b 的二維前綴和是 a
同樣只有一個(gè)操作記住下面這張圖：
想要綠色部分的 a 在 o(1) 的時(shí)間內(nèi)全部加上 c 則只需要在 b 的圖中 +c 的位置 +c -c 的位置 -c。就可以了
def add(x1,y1, x2, y2, v):
b[x1][y1] += v
b[x2+1][y1] -= v
b[x1][y2+1] -= v
b[x2+1][y2+1] += v
