sko.kr

アルゴリズム - 4. 累積和

algorithmsarraysoptimizationprefix-sumsrange-queries
By sko•9/29/2025•5 min read

累積和を使うべき場合

配列内の範囲に対する累積プロパティを繰り返しクエリする必要がある場合に累積和を使用します。最も一般的には範囲和に使用されますが、以下のように応用できます：

  • 範囲和クエリ（古典的なユースケース）
  • 部分配列和問題（目標和を持つ部分配列を見つける）
  • 累積頻度（範囲内の要素をカウント）
  • 範囲積（対数または別配列を使用した変更で）
  • 2D行列領域和（2D累積和への拡張）
  • 差分配列（範囲更新を効率的に適用）
  • 区間上の累積プロパティの複数クエリを必要とする問題

例題

日次売上分析：日次売上データ[3, 5, 2, 8, 4, 6, 1]が与えられ、異なる日付範囲の売上に関する複数のクエリに答える必要があります。

  • クエリ：「2日目から5日目までの総売上は？」
  • クエリ：「0日目から3日目までの総売上は？」
  • クエリ：「4日目から6日目までの総売上は？」

答え：累積和配列を一度構築すれば、各クエリをO(1)時間で答えられます。2日目から5日目まで：合計は20（2 + 8 + 4 + 6）です。

最も重要な洞察

任意の範囲和は2つの累積和の差に等しい - 開始からの累積和を事前計算することで、減算を使用して任意の部分配列和を瞬時に計算できます：sum(i, j) = prefix[j] - prefix[i-1]。

メモ：このアルゴリズムの力は問題の変換にあります。要素を繰り返し合計する（クエリごとにO(n)）代わりに、すべての部分和を一度だけ事前計算します。クエリ時には、「右境界までの合計」から「左境界前の合計」を引くだけです。これにより、繰り返しのO(n)操作がO(1)ルックアップに変換されます。

なぜ「累積和（Prefix Sum）」？：この名前は、配列の各接頭辞（先頭部分）の和を格納することに由来します。配列[3, 5, 2, 8]の場合、接頭辞は[3]、[3, 5]、[3, 5, 2]、[3, 5, 2, 8]です。それらの和を格納します：[0, 3, 8, 10, 18]。このテクニックが「Prefix Sum」と呼ばれるのは、古典的なユースケースが加算だからです—同じパターンは他の操作（累積積など）でも機能しますが、あまり一般的ではありません。

単位元が重要：初期値は操作に依存します：加算には0（x + 0 = xなので）、乗算には1（x × 1 = xなので）。累積積の場合、prefix[0] = 1を使用し、逆操作（除算）を使用して範囲を抽出します：product(left, right) = prefix[right+1] / prefix[left]。これは、減算が加算の逆操作であることと同様です。

判断フレームワーク

累積和テクニックは2つのフェーズで構成されます：

構築フェーズ：配列を一度走査しながら、操作（加算、乗算など）を使用して値を累積

クエリフェーズ：任意の範囲[left, right]に対して、2つの事前計算値に逆操作を使用して範囲結果を抽出

  • 加算 → 減算：sum(left, right) = prefix[right+1] - prefix[left]
  • 乗算 → 除算：product(left, right) = prefix[right+1] / prefix[left]
  • 最大値 → 最大値（冪等）：max(left, right) = max(prefix[right+1], -prefix[left])（セグメント木などの異なるアプローチが必要）

コード

// 構築フェーズ：すべての累積和を事前計算
function buildPrefixSum(nums) {
  // 空の接頭辞を表す0から始める
  const prefix = new Array(nums.length + 1).fill(0);

  for (let i = 0; i < nums.length; i++) {
    const currentNum = nums[i];
    const sumSoFar = prefix[i];

    // 判断フレームワーク：累積合計を蓄積
    prefix[i + 1] = sumSoFar + currentNum;
  }

  return prefix;
}

// クエリフェーズ：逆操作を使用して範囲を抽出
function rangeSum(prefix, left, right) {
  const totalUpToRight = prefix[right + 1];
  const totalBeforeLeft = prefix[left];

  // 判断フレームワーク：減算で範囲を抽出
  return totalUpToRight - totalBeforeLeft;
}

// 日次売上データでの使用例
const dailySales = [3, 5, 2, 8, 4, 6, 1];
const prefixSums = buildPrefixSum(dailySales);

console.log(rangeSum(prefixSums, 2, 5)); // 20（2〜5日目：2+8+4+6）
console.log(rangeSum(prefixSums, 0, 3)); // 18（0〜3日目：3+5+2+8）
console.log(rangeSum(prefixSums, 4, 6)); // 11（4〜6日目：4+6+1）

疑問解消

よくある疑問：「なぜ累積和配列の先頭に余分な要素を追加するのか？元の配列と同じインデックスを使用できないのか？」

余分な要素を避けたい理由

一対一の対応がある方が直感的に見えます：

  • 元の配列：[3, 5, 2, 8, 4, 6, 1]
  • 累積和配列：[3, 8, 10, 18, 22, 28, 29]（同じ長さ）

この方法では、prefix[i]が0からiまでの要素の和となり、自然に感じられます。

余分な要素が重要な理由

重要な認識：余分な要素がないと、インデックス0から始まる範囲に対して特殊なケース処理が必要になります！

余分な要素がない場合に何が起こるか見てみましょう：

元の配列： [3, 5, 2, 8, 4, 6, 1]
累積和：    [3, 8, 10, 18, 22, 28, 29]

クエリ sum(2, 5)：
  = prefix[5] - prefix[1]
  = 28 - 8
  = 20 ✓（正しい：2+8+4+6）

クエリ sum(0, 3)：
  = prefix[3] - prefix[-1]  // おっと！インデックス-1は存在しない
  = prefix[3] - ???
  = 特殊ケースが必要：if (left == 0) return prefix[right]

エレガントな解決策：prefix[0] = 0

先頭にゼロを追加することで：

元の配列： [3, 5, 2, 8, 4, 6, 1]
累積和：    [0, 3, 8, 10, 18, 22, 28, 29]
           ↑
           これは「ゼロ要素の和」を表す

クエリ sum(0, 3)：
  = prefix[4] - prefix[0]
  = 18 - 0
  = 18 ✓（正しい：3+5+2+8）

このパターンが正しさを保証する理由

式sum(left, right) = prefix[right+1] - prefix[left]が普遍的に機能する理由：

  1. prefix[i] = 最初のi要素の和（インデックスiの要素を含まない）
  2. prefix[right+1] = インデックスrightまでのすべての要素の和（rightを含む）
  3. prefix[left] = インデックスleft前のすべての要素の和
  4. その差が範囲[left, right]の要素を正確に与える

これにより、すべての特殊ケースが排除され、コードがよりクリーンで、保守しやすく、エラーが発生しにくくなります。余分なメモリコスト（1要素）は、得られる明瞭さに比べれば無視できます。

← Back to Blog