返回工具主页
前缀和数组：快速区间求和
通过预处理构造前缀和数组，将多次区间求和查询从 O(n) 优化到 O(1)。
适用于：数组不变、区间查询频繁的场景
核心思想
给定数组 a = [a₀, a₁, a₂, ..., aₙ₋₁]，构造前缀和数组 s，使得：
s[0] = 0, s[i] = a[0] + a[1] + ... + a[i-1] (1 ≤ i ≤ n)
那么区间 [l, r] 的和（包含两端）可一步算出：
sum(l, r) = s[r + 1] - s[l]
数组与前缀和
原始数组 a
前缀和数组 s（s[0] = 0）
提示：可直接点击上方原始数组中的数字修改
区间求和对比
查询区间 [l, r]：
暴力枚举法
从 l 到 r 逐个相加
时间复杂度：O(r - l + 1)，即 O(n)
前缀和法
直接利用 s[r+1] - s[l]
时间复杂度：O(1)（查询时）
教学提示：
前缀和用 O(n) 的预处理时间，换取每次 O(1) 的区间查询。当查询次数很多时，效率提升非常显著。
Python 实现
前缀和 + 区间查询
# 构造前缀和数组
def build_prefix(a):
n = len(a)
s = [0] * (n + 1)
for i in range(1, n + 1):
s[i] = s[i - 1] + a[i - 1]
return s
# 查询区间 [l, r] 的和（包含两端）
def range_sum(s, l, r):
return s[r + 1] - s[l]