calendar_month 0001-01-01
schedule 2025-12-21
edit_square 127 字
这篇文章介绍了前缀和的概念，它是一种通过提取并存储数组元素的前缀特性来提高问题处理效率的方法。文章通过两个示例展示了前缀和的应用：第一个示例是计算非负数组的任意区间和，第二个示例是处理区间元素叠加操作后求数组最大值的问题，并阐述了使用前缀和优化算法以提高效率的原理。
前缀和将元素的前缀特性提取并存储到一个数组中方便检索，利用元素的前缀特性能够提高某些问题的处理效率。
假设$arr$为输入的数据：
声明一个前缀数组$pf$。 对$arr$进行循环，对$arr$当前元素和$pf$的上一个元素(或$pf$当前元素)求和然后赋值给$pf$当前元素(或$pf$的下一个元素) 非负数组任意区间的求和(起始索引为1)
def interval_sum(arr, query):
n = len(arr)
pf = [0 for i in range(n+1)]
for i in range(n):
pf[i+1] = pf[i] + arr[i]
for i in range(len(query)):
print(pf[query[i][1]] - pf[query[i][0]-1])
# Driver code
arr = [10, 4, 16, 20]
query = [
[2,3], # 20
[1,2], # 14
]
interval_sum(arr, query)
给定一个初始值为0的数组$arr$，进行$m$轮对区间$[a_x,b_x]$元素叠加100操作后，求arr中的最大值(起始索引为1)
传统方法是对数组arr进行m轮叠加后再线性比对的方式找最大值，时间复杂度为$O(m*n)$。若对$arr[a]$加100并同时对$arr[b+1]$减100，会对arr的前缀和数组产生区间$[a,b]$同时加100的效果，最后再通过线性比对寻找前缀数组的最大值即可，时间复杂度为$O(m+n)$。
def max_value(size, query):
arr = [0 for i in range(size)]
max_val = float('-inf')
pf_val = 0
for i in range(len(query)):
arr[query[i][0]-1] += 100
arr[query[i][1]] -= 100
for i in range(size):
pf_val += arr[i]
if pf_val > max_val:
max_val = pf_val
return max_val
# Driver code
size = 5
query = [
[2, 4],
[1, 3],
[1, 2],
]
print(max_value(size, query))