Zenn
😎

【競技プログラミング典型アルゴリズム】累積和

2024/11/13に公開
C#
アルゴリズム
累積和
tech

はじめに

一次元部分和や二次元部分和の競技プログラミングの問題が出たのでまとめています．
一次元部分和と二次元部分和は、累積和（Prefix Sum）に基づく手法です。それぞれ、1次元または2次元の配列に対して、部分区間の合計を効率的に計算するために使われます。これにより、区間の和のクエリを高速に処理できます。

一次元部分和（1D Prefix Sum）

概要

  • 一次元配列に対して、ある区間の要素の合計を効率的に求めるための手法です。
  • 前もって累積和を計算しておき、区間の和を O(1) の時間で取得できます。

具体例

  • 配列 A = [2, 4, 5, 7, 1, 3] があるとします。
  • 部分和配列 S を次のように計算します。

累積和の計算方法

S[i] = A[0] + A[1] + \ldots + A[i-1]

累積和 S は次のようになります:

S[0] = 0 （初期値）\\ S[1] = 2\\ S[2] = 2 + 4 = 6\\ S[3] = 6 + 5 = 11\\ S[4] = 11 + 7 = 18\\ S[5] = 18 + 1 = 19\\ S[6] = 19 + 3 = 22\\

よって、累積和配列 S = [0, 2, 6, 11, 18, 19, 22]

区間和の計算

  • 例えば、配列 A の区間 [l, r]（0-based index）の合計を求める場合:
\text{sum}(A[l] \text{ から } A[r]) = S[r + 1] - S[l]
  • 例: 区間 [2, 4] の合計は:
S[5] - S[2] = 19 - 6 = 13

また、

A[2] + A[3] + A[4] = 5 + 7 + 1 = 13

実装例（C#）

int[] A = { 2, 4, 5, 7, 1, 3 };
int N = A.Length;
int[] S = new int[N + 1];

// 累積和の計算
for (int i = 0; i < N; i++)
{
    S[i + 1] = S[i] + A[i];
}

// 区間 [2, 4] の和を計算
int left = 2, right = 4;
int sum = S[right + 1] - S[left]; // 13
Console.WriteLine($"区間 [{left}, {right}] の和: {sum}");

二次元部分和（2D Prefix Sum）

概要

  • 二次元配列（行列）に対して、ある矩形領域の合計を効率的に求めるための手法です。
  • 事前に累積和の2次元配列を計算しておくことで、任意の矩形領域の合計を O(1) で取得可能です。

具体例

  • 配列 A:
\begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ \end{matrix}

累積和の計算方法

S[i][j] = A[0][0] + A[0][1] + \ldots + A[0][j] + \ldots + A[i][j]
  • 累積和 S は次のようになります:
\begin{matrix} 1 & 3 & 6 \\ 5 & 12 & 21 \\ 12 & 27 & 45 \\ \end{matrix}

矩形領域の計算

  • 矩形領域 (r1, c1) から (r2, c2) の合計を求める場合:
\text{sum} = S[r2+1][c2+1] - S[r1][c2+1] - S[r2+1][c1] + S[r1][c1]
  • 例えば、領域 (1, 1) から (2, 2) の合計:
S[3][3] - S[1][3] - S[3][1] + S[1][1]\\ 45 - 6 - 12 + 1 = 28

実装例（C#）

int[,] A = {
    { 1, 2, 3 },
    { 4, 5, 6 },
    { 7, 8, 9 }
};
int R = A.GetLength(0);
int C = A.GetLength(1);
int[,] S = new int[R + 1, C + 1];

// 二次元累積和の計算
for (int i = 0; i < R; i++)
{
    for (int j = 0; j < C; j++)
    {
        S[i + 1, j + 1] = A[i, j] + S[i, j + 1] + S[i + 1, j] - S[i, j];
    }
}

// 領域 (1, 1) から (2, 2) の和を計算
int r1 = 1, c1 = 1, r2 = 2, c2 = 2;
int sum = S[r2 + 1, c2 + 1] - S[r1, c2 + 1] - S[r2 + 1, c1] + S[r1, c1];
Console.WriteLine($"領域 [{r1}, {c1}] から [{r2}, {c2}] の和: {sum}");

まとめ

  • 一次元部分和は、1次元配列の区間和を高速に計算します。前処理は ( O(N) )、クエリは ( O(1) )。
  • 二次元部分和は、2次元配列の矩形領域の合計を高速に計算します。前処理は ( O(N \times M) )、クエリは ( O(1) )。
  • これらの手法は、特に競技プログラミングやデータ分析などで、大量のクエリ処理が必要な場合に非常に有効です。

おすすめ・参考書籍

https://amzn.to/3YFmdH5

Discussion