🙄
【C#アルゴリズム】二次元いもす法
はじめに
paiza で二次元いもす法を用いる問題が出てきたのでそれについてまとめます。
累積和の応用アルゴリズムとなるため、累積和に関する記事もあわせて読んでみてください。
一次元いもす法についてもあわせて読んでみてください。
二次元いもす法について
二次元いもす法は、二次元平面（グリッド）上の範囲指定による操作を効率的に行う手法です。
1次元のいもす法を二次元グリッドに拡張したもので、範囲指定された領域への加算や累積計算を効率化します。
基本原理
1次元いもす法では、「区間の始点と終点」に操作の影響を記録しましたが、二次元いもす法では次の4点に影響を記録します。
- 領域の左上（加算）
- 領域の右上（減算）
- 領域の左下（減算）
- 領域の右下（加算）
これにより、累積的な影響を記録し、最終的に累積和を取ることで各マスの値を効率的に求められます。
数式での説明
領域
- 左上に加算：
A[x_1 -1 , y_1 -1 ] += v - 右上に減算：
A[x_2, y_1 - 1] -= v - 左下に減算：
A[x_1 -1 , y_2] -= v - 右下に加算：
A[x_2, y_2] += v
その後、累積和を次の順序で取ります：
- 横方向に累積和
- 縦方向に累積和
C#コードの解説
以下のコードでは、
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static void Main()
{
int X = 5; // グリッドの幅
int Y = 5; // グリッドの高さ
// 各操作の範囲を指定する座標
int[] lx = { 1, 2, 3, 1, 3 }; // 左上のx座標
int[] ly = { 1, 2, 3, 3, 1 }; // 左上のy座標
int[] rx = { 3, 4, 5, 3, 5 }; // 右下のx座標
int[] ry = { 3, 4, 5, 5, 3 }; // 右下のy座標
int[,] A = new int[X + 1, Y + 1]; // 影響を記録する配列（余白を作る）
int Q = 5; // 操作の数
for (int i = 0; i < Q; i++)
{
// 各範囲の影響を記録
A[lx[i] - 1, ly[i] - 1]++; // 左上
A[rx[i], ly[i] - 1]--; // 右上
A[lx[i] - 1, ry[i]]--; // 左下
A[rx[i], ry[i]]++; // 右下
}
// 横方向の累積和
for (int y = 0; y <= Y; y++)
{
for (int x = 1; x <= X; x++)
{
A[x, y] += A[x - 1, y];
}
}
// 縦方向の累積和
for (int x = 0; x <= X; x++)
{
for (int y = 1; y <= Y; y++)
{
A[x, y] += A[x, y - 1];
}
}
// 最大値を求める
int max = 0;
foreach (var item in A)
{
max = Math.Max(max, item);
}
Console.WriteLine(max);
}
}
応用例
- 最大重複範囲の計算
- 複数の矩形があるとき、最も重なっている領域に何枚の矩形が重なっているかを求める。
- 人口密度の計算
- ゲーム開発（マップの範囲効果）
おすすめ・参考書籍
問題解決力を鍛える！アルゴリズムとデータ構造 (ＫＳ情報科学専門書)
累積和に関する記事
一次元いモス式に関する記事
Discussion