05_前缀和

前缀和

用途：快速求区间和，查询时间 O(1)，预处理 O(n)

原理：prefix[i] 表示前 i 个元素的和，区间 [l, r] 的和 = prefix[r] - prefix[l-1]

# 一维前缀和
prefix = [0] * (n + 1)
for i in range(n):
  prefix[i + 1] = prefix[i] + a[i]  # a 是 0-indexed

# 查询区间 [l, r]（1-indexed）
def query(l, r):
  return prefix[r] - prefix[l - 1]

# 二维前缀和
prefix = [[0] * (m+1) for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, m+1):
        prefix[i][j] = grid[i-1][j-1] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]