calendar_month  schedule  web_traffic 加载中...   edit_square127 字  timer1 分钟 
🤖 AI文章摘要 qwen-turbo-latest
加载中...
此内容根据文章生成，并经过人工审核，仅用于文章内容的解释与总结 投诉

前缀和

前缀和将元素的前缀特性提取并存储到一个数组中方便检索，利用元素的前缀特性能够提高某些问题的处理效率。

假设$arr$为输入的数据：

  • 声明一个前缀数组$pf$。
  • 对$arr$进行循环，对$arr$当前元素和$pf$的上一个元素(或$pf$当前元素)求和然后赋值给$pf$当前元素(或$pf$的下一个元素)

使用示例

前缀和示例1

非负数组任意区间的求和(起始索引为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)

前缀和示例2

给定一个初始值为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))