• 前綴和有利于快速求解 區間的和、異或值 、乘積等情況
• 差分是前綴和的反操作

前綴和

• 一維前綴和：

# 原始的數組num,下標從1到n
n = len(num)
pre = [0]*(n+1)
for i in range(n):pre[i+1] = pre[i] + num[i]
# 如果需要求解num[l] 到num[r] 的區間和
ans = pre[r] - pre[l-1]

• 二維前綴和

# 原本的數組是n*m形狀的pre = [[0]*(m+1) for _ in range(n+1)]for i in range(n):for j in range(m):pre[i+1][j+1] = pre[i][j+1] + pre[i+1][j] - pre[i][j] + num[i][j]

前綴和的應用：

• 當你想在一個區間進行統一的加上一個數或者減去一個數的時候，一個個操作會很慢，并且涉及多次操作的時候更新很麻煩，但是我們可以結合這個差分和前綴和進行快速求解

• 一維：

# 在區間l到r之間同時都加上a,那么我們只需在num[l] + a,在num[r+1] -a
# 然后求解前綴和即可，就可以得到每個位置的最后的值

• 二維：

# 1<=x1<=x2<=y1<=y2<=n
# 在x1,y1 到 x2,y2 之間都加上一個數
num[x1][y1] += a
num[x2+1]y2+1] +=a
num[x1][y2+1] -=a
num[x2+1][y1] -=a

差分：

• 一維差分：

# 1<=l<=r<=n ，那么區間l到r之間的和值為
ans = pre[r] - pre[l-1]

• 二維查分：

# 
ans = pre[x2][y2] - pre[x2][y1] - pre[x1][y2] + pre[x1][y1]

題目

求和

求和

思路分析：

• 首先直接暴力是肯定不行的，所以得考慮轉換？發現可以提取相同的元素，然后使用這個前綴和進行優化即可

import os
import sys# 請在此輸入您的代碼# 提取公因式，你會發現 ans = a1*(a2+···an) + a2*(a3+···an) + an-1*(an)n = int(input())
num = list(map(int,input().split()))pre = [0]*(n+1)
for i in range(n):pre[i+1] = pre[i] + num[i]ans = 0
for i in range(n-1):ans += num[i]*(pre[n]-pre[i+1])
print(ans)

棋盤

棋盤

思路分析：

• 這個題目得使用到這個二維的前綴和與查分進行優化

import os
import sys# 請在此輸入您的代碼# 其實和這個，異或操作是類似的
# 0表示白色，1表示黑色n,m = map(int,input().split())num = [[0]*(n+1) for _ in range(n+1)]for _ in range(m):x1,y1,x2,y2 = map(int,input().split())x1,y1,x2,y2 = x1-1,y1-1,x2-1,y2-1num[x1][y1] += 1num[x2+1][y2+1]     +=1num[x1][y2+1]   -=1num[x2+1][y1]   -=1# 求解二維前綴和
dp = [[0]*(n+1) for _ in range(n+1)]for i in range(n):for j in range(n):dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1] - dp[i][j] + num[i][j])%2for i in range(1, n + 1):row = "".join(str(dp[i][j]) for j in range(1, n + 1))print(row)

挖礦

挖礦

思路分析：

• 首先明確一個問題，在坐標軸上移動，最多只能轉向一次：證明，設你轉向多次之后到達左端點是 l,到達右端點的坐標是 r,如果你直接一開始不轉向，直接到達左端點l,然后再直接向后轉向右邊,那么到達的距離是肯定比r大的

import os
import sys# 請在此輸入您的代碼
n,m = map(int,input().split())
num = list(map(int,input().split()))
# 開的空間
l ,r = [0]*(m + 1),[0]*(m + 1)iszero = 0for i in num:if i > 0 and i <= m:r[i] += 1if i < 0 and abs(i) <= m:l[abs(i)] += 1if i == 0:iszero = 1# 計算出其中的左和右可以到達的位置所能得到的礦
for i in range(1,m+1):r[i] += r[i-1]l[i] += l[i-1]
ans = 0# 枚舉可以到達的端點，注意左邊和右邊
for j in range(1,m//2 + 1):ans = max(ans,r[j] + l[m-2*j],l[j] + r[m-2*j])print(ans+iszero)