プレフィックス和とは何か、また範囲クエリをどのように高速化するか？

Question

Accepted Answer

**プレフィックス和**配列は累積合計を格納し、**範囲和**が O(n) の前処理後に **O(1)** で答えられます。クエリごとに O(n) ではなく。

## アイデア

`prefix[i]` を最初の `i` 個の要素の合計とします。すると、`arr[l..r]` の合計は `prefix[r+1] - prefix[l]` です。

## 例

```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
```

## トレース

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

## 計算量

- **構築:** O(n)。**クエリ:** O(1)。**空間:** O(n)。

## 使用時期 / 落とし穴

静的データの**多数の範囲和クエリ**に最適です。変種: 部分行列の合計のための2Dプレフィックス和、プレフィックス XOR、範囲更新のための差分配列。配列が頻繁に変わる場合は、代わりに Fenwick ツリー/セグメントツリーを使用します。インデックスオフセットに注意してください（サイズ n+1）。

## なぜ重要なのか

プレフィックス和は、繰り返される O(n) の範囲クエリを O(1) のルックアップに変えます — クエリが頻繁な場合に大きな利点です。

前計算一度、高速に答える パターンは、多くのデータ処理タスクに一般化します。

競技プログラミングの基本要素であり、分析における一般的な構築ブロックです。