🎯

【Java】二次元のいもす法

2024/05/01に公開

Java

初心者

tech

二次元のいもす法

二次元のいもす法とは、0で初期化された二次元配列の矩形領域内の各要素に同じ数を足した二次元配列を求める時に、累積和を用いることにより高速に求めることができるアルゴリズムです。
前回同様、二次元配列aを累積和の二次元配列に変換することで求めたい二次元配列を用意します。
そして、こちらも同様に、累積和の二次元配列において要素数0個を考慮しません。

二次元のいもす法の図解

まずは、従前の記事の二次元累積和の区間の和について下記を参考にしてください。

次に二次元配列の矩形領域内の各要素に同じ数を加える方法とその二次元累積和の区間の和を一般化した図が、下記の通りになります。

二次元のいもす法のアルゴリズム

サイズn+1×m+1の二次元配列aを0で初期化。
q回にわたって区間(x1, y1)→(x2, y2)にxを足す。
1. q回、a[x2+1][y2+1]にx、a[x2+1][y1]に-x、a[x1][y2+1]に-x、a[x1][y1]にxを加算します。
  - iを0からq-1までループするfor文を定義して、
  - a[x2 + 1][y2 + 1] += x、a[x2 + 1][y1] -= x、a[x1][y2 + 1] -= x、a[x1][y1] += xを加算します。
2. 二次元配列aを累積和の二次元配列にする。
  - 配列aの各行を先頭0個の和を考慮しない累積和にします。
    - iを0からn-1まで繰り返すfor文を定義して、
    - さらにjを1からm-1まで繰り返すfor文を定義して、
    - a[i][j]にa[i][j-1]を加算します。
  - 配列aの各列を先頭0個の和を考慮しない累積和にします。
    - jを0からm-1まで繰り返すfor文を定義して、
    - さらにiを1からn-1まで繰り返すfor文を定義して、
    - a[i][j]にa[i-1][j]を加算します。

コード例

今回もコード例の解説は割愛します。

import java.util.*;

public class Main {

    static void print2DArray(int[][] a, int n, int m) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (j != 0) {
                    System.out.print(" ");
                }
                System.out.print(a[i][j]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n, m, q;
        n = sc.nextInt();
        m = sc.nextInt();
        q = sc.nextInt();

        // 二次元配列 a をサイズ n+1 × m+1 で用意
        int[][] a = new int[n + 1][m + 1];
        
        for (int i = 0; i < q; i++) {
            int x1, y1, x2, y2, x;
            x1 = sc.nextInt();
            y1 = sc.nextInt();
            x2 = sc.nextInt();
            y2 = sc.nextInt();
            x = sc.nextInt();

            // a[x2+1][y2+1] に x, a[x2+1][y1] に -x, a[x1][y2+1] に -x, a[x1][y1] に x を加算
            a[x2 + 1][y2 + 1] += x;
            a[x2 + 1][y1] -= x;
            a[x1][y2 + 1] -= x;
            a[x1][y1] += x;
        }
        
        // 二次元配列 a の各行を先頭0個の和を考慮しない累積和にする
        for (int i = 0; i < n; i++) {
            // j を 1 から m-1 まで繰り返す
            for (int j = 1; j < m; j++) {
                // a[i][j] に a[i][j-1] を加算
                a[i][j] += a[i][j - 1];
            }
        }
        
        // 二次元配列 a の各列を先頭0個の和を考慮しない累積和にする
        for (int j = 0; j < m; j++) {
            // i を 1 から n-1 まで繰り返す
            for (int i = 1; i < n; i++) {
                // a[i][j] に a[i-1][j] を加算
                a[i][j] += a[i - 1][j];
            }
        }
        
        // 二次元配列 a を出力
        print2DArray(a, n, m);
    }
}

入力値

5 5 1
1 1 3 3 8

出力結果

二次元のいもす法

二次元のいもす法の図解

二次元のいもす法のアルゴリズム

コード例

Discussion