Zenn
😊

【競技プログラミングでの典型アルゴリズム】平方分割

2024/11/13に公開
C#
競技プログラミング
アルゴリズム
tech

はじめに

平方分割という手法があり，汎用性が高そうなのでまとめました。
平方分割（Square Root Decomposition）とは、データ構造やアルゴリズムの一つで、大きな配列やリストに対する区間クエリ（例えば、区間の和・最大値・最小値など）や更新操作を効率的に行うための手法です。この手法の名前は、問題を解決するために配列をほぼ等しい大きさの√N個のブロックに分割することから来ています。

平方分割のアイデア

  • 長さが N の配列を ブロックサイズ √N に分割し、それぞれのブロックに対して事前に必要な情報（例えば、各ブロックの合計や最大値など）を計算して保持しておきます。
  • クエリ処理の際には、分割されたブロック全体を処理することで、全体の計算量を削減します。

平方分割のメリット

  • 区間クエリ（Range Query） を効率的に処理できます。
  • 配列を単純に走査するよりも速い処理が可能です。
  • クエリが（O(√N)）の計算量で処理できるため、配列全体を処理する (O(N)) よりも効率的です。

典型的な平方分割の処理手順

例題：区間の最大値を求める

配列 A から、いくつかの区間に対して最大値を求める処理を考えます。

  1. 前処理（Preprocessing）:

    • 配列 A を √N の長さのブロックに分割します。
    • 各ブロックについて、そのブロック内の最大値を事前に計算して保存しておきます。

  2. クエリ処理:

    • クエリの範囲が複数のブロックにまたがる場合、以下の3つの部分に分けて処理します：
      • 左端の部分ブロック（クエリの開始点から次のブロックの開始まで）
      • 中間の完全なブロック（クエリ範囲全体がブロックに収まる場合）
      • 右端の部分ブロック（最後の完全なブロックからクエリの終了点まで）
    • 左端と右端の部分は1つずつ処理し、中間の完全なブロックは事前に計算した最大値を利用して高速に処理します。

平方分割の実装例（C#）

以下は、平方分割を使って区間の最大値を求めるC#の例です。

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        int N = 10; // 配列の長さ
        int[] A = { 1, 5, 2, 4, 6, 1, 3, 5, 7, 10 }; // 入力配列
        int sqrt = (int)Math.Sqrt(N);

        // 必要に応じてブロックサイズを調整
        if (sqrt * sqrt < N)
            sqrt++;

        // ブロックごとの最大値を格納する配列
        int[] maxBlock = new int[sqrt];
        for (int i = 0; i < sqrt; i++)
        {
            int start = i * sqrt;
            int end = Math.Min(start + sqrt, N);
            maxBlock[i] = A[start];
            for (int j = start + 1; j < end; j++)
            {
                maxBlock[i] = Math.Max(maxBlock[i], A[j]);
            }
        }

        // クエリ処理（例として、区間[2, 8]の最大値を求める）
        int left = 2, right = 8;
        int max = int.MinValue;
        int index = left;

        // クエリ処理にwhileループを使用
        while (index <= right)
        {
            // ブロックの開始位置にいて、かつブロック全体が範囲内に収まる場合
            if (index % sqrt == 0 && index + sqrt - 1 <= right)
            {
                max = Math.Max(max, maxBlock[index / sqrt]);
                index += sqrt; // 次のブロックにジャンプ
            }
            else
            {
                // ブロック内の要素を1つずつ確認
                max = Math.Max(max, A[index]);
                index++;
            }
        }

        // 結果を出力
        Console.WriteLine($"区間 [{left}, {right}] の最大値: {max}");
    }
}

時間計算量の解析

  • 前処理:（O(N)）
    • 各ブロックの最大値を計算するため、全体で（O(N)）の計算が必要です。
  • クエリ処理:（O(√N)）
    • 左端と右端の部分はそれぞれ高々（O(√N)）かかります。
    • 中間のブロックの数も高々（O(√N)）なので、クエリ全体の処理は（O(√N)）になります。

平方分割の用途

  • 区間和、区間の最小値・最大値、頻度計算などのクエリ処理。
  • 部分更新（例えば1つの要素の更新） もサポート可能。
  • 競技プログラミングやデータ分析において、大きなデータに対する効率的な処理が求められる場合によく使われます。

まとめ

  • 平方分割は、単純な配列操作よりも効率的にクエリ処理が可能な手法です。
    平方分割は、シンプルかつ強力なテクニックの一つとして覚えておくと良いでしょう。

おすすめ・参考書籍

https://amzn.to/3YFmdH5

Discussion