什么是前缀和，它如何加速范围查询？

Question

什么是前缀和，它如何加速范围查询？

Accepted Answer

一个**前缀和** array 存储累计总和，这样任何**范围和** 在 O(n) 预处理后可以在 **O(1)** 内回答 — 而不是每个查询 O(n)。

## The idea

让 `prefix[i]` 是前 `i` 个元素的和。那么 `arr[l..r]` 的和是 `prefix[r+1] - prefix[l]`。

## Example

```python
def build_prefix(arr):
    prefix = [0] * (len(arr) + 1)
    for i, x in enumerate(arr):
        prefix[i + 1] = prefix[i] + x   # running total
    return prefix

def range_sum(prefix, l, r):            # inclusive l..r
    return prefix[r + 1] - prefix[l]    # O(1)

p = build_prefix([2, 4, 1, 3, 5])
range_sum(p, 1, 3)                      # 4+1+3 -> 8
```

## Trace

```text
arr    = [2, 4, 1, 3, 5]
prefix = [0, 2, 6, 7, 10, 15]
sum(1..3) = prefix[4] - prefix[1] = 10 - 2 = 8
```

## Complexity

- **Build:** O(n)。**Query:** O(1)。**Space:** O(n)。

## 何时使用 / 陷阱

理想用于**对静态数据进行多次范围和查询**。变种：2D 前缀和用于子矩阵和、前缀 XOR 和差分数组用于范围更新。如果数组经常变化，改用 Fenwick/segment tree。注意索引偏移（大小 n+1）。

## 为什么这很重要

前缀和将重复的 O(n) 范围查询转变为 O(1) 查找 — 当查询频繁时这是巨大的优势。

预计算一次、快速回答的模式推广到许多数据处理任务。

它是竞技编程的常规工具，也是分析中的常见构建块。