Zenn
🙄

【C#アルゴリズム】一次元いもす法

2024/11/30に公開
C#
アルゴリズム
tech

はじめに

paiza　でいもす法を用いる問題が出てきたのでそれについてまとめます。
累積和の応用アルゴリズムとなるため、累積和に関する記事もあわせて読んでみてください。

https://zenn.dev/student_blog/articles/7fc669f848841d

いもす法について

いもす法は、区間に対する累積的な影響を効率的に計算するアルゴリズムです。
特に、区間加算や区間変更などの操作が多い場合に計算量を大幅に削減するために使用されます。
基本的なアイデアは、影響範囲の開始と終了だけを記録し、最終的に累積和を取るというものです。
累積和と違い、要素の変更が繰り返し行われる場合に有効です。

基本原理

問題の例

長さ N の配列 A に対して、次の操作を効率的に処理することを考えます：

  1. 区間 [l, r] に値 v を加える操作を Q 回行う。
  2. 最終的な配列 A を出力する。

通常の方法では、各操作で区間全体をループして値を加えるため、計算量は O(N \times Q) になります。

いもす法の考え方

いもす法では、次のようにして効率化を図ります：

  1. 影響範囲の記録
    区間の開始位置 l - 1 に +v、終了位置 r に -v を記録する。

    配列の変化を記録するために、別の配列 A を用意します：

    • A[l-1] += v
    • A[r] -= v

  2. 累積和の計算
    配列 $A の累積和を取ることで、最終的な配列の各要素を計算します。
    これにより、計算量は O(N + Q) となります。

数式での説明

  1. 操作による配列への影響を記録：
    A[i] = A[i] + v \quad \text{(for } i = l - 1\text{)}
    A[i] = A[i] - v \quad \text{(for } i = r\text{)}

  2. 累積和を計算して最終的な配列を得る：
    A[i + 1] = A[i + 1] + A[i]

C#での実装例

次の例では、長さ N = 10 の配列に対して、複数の区間加算操作を行い、最終的な配列を出力します。

using System;
using System;
class Program
{
   static void Main()
   {
       int N = 10;
       int Q = 5;
       int[] from = { 1, 1, 3, 3, 7 };
       int[] to = { 3, 8, 8, 6, 9 };

       int[] A = new int[N + 1];
       for (int i = 0; i < Q; i++)
       {
           A[from[i] - 1]++;
           A[to[i]]--;
       }

       for (int i = 0; i < N; i++)
       {
           A[i + 1] += A[i];
       }

       Console.WriteLine(A.Max());
   }
}

応用例

  1. 区間加算問題
    多数の区間加算操作を効率的に処理する。

  2. 2次元いもす法
    グリッドに対していもす法を拡張し、領域への操作を効率化する。

おすすめ・参考書籍

問題解決力を鍛える！アルゴリズムとデータ構造 (ＫＳ情報科学専門書)
https://amzn.to/3YFmdH5

累積和に関する記事
https://zenn.dev/student_blog/articles/7fc669f848841d

Discussion