二次元累積和《累積和》

累積和メニュー

hogeちゃん

2022.08.30

累積和メニュー【二次元累積和 1 〜 7】

問題【STEP: 1】二次元累積和 1

Task

二次元配列 A の長方形領域内の整数の和を累積和を用いて求めてね。

【二次元累積和 1】コード

const A = [
   [1, 2, 3, 4, 5],
   [2, 3, 4, 5, 6],
   [3, 4, 5, 6, 7],
   [4, 5, 6, 7, 8],
   [5, 6, 7, 8, 9]
];  // 元の値(二次元配列)
const S = [
   [0, 0, 0, 0, 0, 0]
];  // S は A の累積和を保存する配列 先頭行の 要素数は 5 + 1 値は全て 0
for (let i = 0; i < 5; i++) {
   S.push([0]);  // S[i + 1]の先頭列の値は 0
   for (let j = 0; j < 5; j++) {
      S[i + 1].push(S[i + 1][j] + A[i][j] + S[i][j + 1] - S[i][j]);
  // A[0][0] ~ A[i][j] の矩形領域の値の総和
   }
}
   // console.log(S);
   // [
   // [ 0, 0, 0, 0, 0, 0 ],
   // [ 0, 1, 3, 6, 10, 15 ],
   // [ 0, 3, 8, 15, 24, 35 ],
   // [ 0, 6, 15, 27, 42, 60 ],
   // [ 0, 10, 24, 42, 64, 90 ],
   // [ 0, 15, 35, 60, 90, 125 ]
   // ]
const [s, e] = [1, 3];  // A[s][s] は 左上,A[e][e] は 右下
console.log(S[e + 1][e + 1] - S[e + 1][s] - S[s][e + 1] + S[s][s]);
  // A[1][1] ~ A[3][3]の矩形領域の総和 = 64 - 10 - 10 + 1

hogeちゃんの画像

配列 A の赤字の部分の和を2次元累積和を使って求めています。配列 S のデータの赤字の部分を加算して青字の部分を減算すれば OKでした。詳しくは問題文中の（ヒント）をご参照下さい。

問題【STEP: 2】二次元累積和 2

Task

5✕5 の二次元配列 A の長方形領域(左上A[1][1], 右下 A[3][3] )の累積和を求めてね。

【二次元累積和 2】コード

reader.on('close', () => {
   const A = [];  // 元の値
   for (let i = 0; i < 5; i++) {
      A.push(lines[i].split(' ').map(Number));
   }
   const S = [
      [0, 0, 0, 0, 0, 0]
   ];  // A の累積和を保存する配列 先頭行の 要素数は 5 + 1 値は全て 0
   for (let i = 0; i < 5; i++) {
      S.push([0]);  // S[i + 1]の先頭列の値は 0
      for (let j = 0; j < 5; j++) {
         S[i + 1].push(S[i + 1][j] + A[i][j] + S[i][j + 1] - S[i][j]);
      }
   }
const [s, e] = [1, 3];  // A[s][s] は 左上,A[e][e] は 右下
   console.log(S[e + 1][e + 1] - S[e + 1][s] - S[s][e + 1] + S[s][s]);
  // A[1][1] ~ A[3][3]の矩形領域の総和 = S[4][4] - S[4][1] - S[1][4] + S[1][1]
});

hogeちゃんの画像

配列 a の値は入力から受け取っています。それ以外は【二次元累積和 1】と同じでした。

問題【STEP: 3】二次元累積和 3

Task

5✕5 の二次元配列 A の長方形領域内(左上A[a][3], 右下A_[b][3])の累積和を求めてね。

【二次元累積和 3】コード

reader.on('close', () => {
   const [a, b] = lines[0].split(' ').map(Number);
   const A = [];
   for (let i = 1; i <= 5; i++) {
      A.push(lines[i].split(' ').map(Number));
   }
   const S = [
      [0, 0, 0, 0, 0, 0]
   ];
   for (let i = 0; i < 5; i++) {
      S.push([0]);
      for (let j = 0; j < 5; j++) {
         S[i + 1].push(S[i + 1][j] + A[i][j] + S[i][j + 1] - S[i][j]);
      }
   }
   console.log(S[b + 1][3 + 1] - S[a][3 + 1] - S[b + 1][3] + S[a][3]);
});

hogeちゃんの画像

配列 A に含まれる長方形領域の左上が A[a][3] ・右下が A[b][3] に指定されました。それ以外は【二次元累積和 2】と同じでした。

問題【STEP: 4】二次元累積和 4

Task

5✕5 の二次元配列 A の長方形領域内(左上A[a][b], 右下A[c][d])の累積和を求めてね。

【二次元累積和 4】コード

reader.on('close', () => {
   const [a, b, c, d] = lines[0].split(' ').map(Number);
   const A = [];
   for (let i = 1; i <= 5; i++) {
      A.push(lines[i].split(' ').map(Number));
   }
   const S = [
      [0, 0, 0, 0, 0, 0]
   ];
   for (let i = 0; i < 5; i++) {
      S.push([0]);
      for (let j = 0; j < 5; j++) {
         S[i + 1].push(S[i + 1][j] + A[i][j] + S[i][j + 1] - S[i][j]);
      }
   }
   console.log(S[c + 1][d + 1] - S[a][d + 1] - S[c + 1][b] + S[a][b]);
});

hogeちゃんの画像

配列 A に含まれる長方形領域の左上が A[a][b] ・右下が A[c][d] に指定されました。

問題【STEP: 5】二次元累積和 5

Task

N✕N の二次元配列 A の長方形領域内(左上 A_{a, b}, 右下 A_{c, d})の累積和を求めてね。

【二次元累積和 5】コード

reader.on('close', () => {
   const N = Number(lines[0]);
   const [a, b, c, d] = lines[1].split(' ').map(Number);
   const A = [];
   for (let i = 2; i < N + 2; i++) {
      A.push(lines[i].split(' ').map(Number));
   }
   const S = [
      []
   ];
   for (let i = 0; i <= N; i++) {
      S[0].push(0);
   }
   for (let i = 0; i < N; i++) {
      S.push([0]);
      for (let j = 0; j < N; j++) {
         S[i + 1].push(S[i + 1][j] + A[i][j] + S[i][j + 1] - S[i][j]);
      }
   }
   console.log(S[c + 1][d + 1] - S[a][d + 1] - S[c + 1][b] + S[a][b]);
});

hogeちゃんの画像

配列 A の要素数が N 行になりました。

問題【STEP: 6】二次元累積和 6

Task

N✕Mの二次元配列 A の長方形領域(左上A_{a, b}, 右下A_{c, d})の累積和を求めてね。

【二次元累積和 6】コード

reader.on('close', () => {
   const [N, M] = lines[0].split(' ').map(Number);
   const [a, b, c, d] = lines[1].split(' ').map(Number);
   const A = [];
   for (let i = 2; i < N + 2; i++) {
      A.push(lines[i].split(' ').map(Number));
   }
   const S = [
      []
   ];
   for (let i = 0; i <= M; i++) {
      S[0].push(0);
   }
   for (let i = 0; i < N; i++) {
      S.push([0]);
      for (let j = 0; j < M; j++) {
         S[i + 1].push(S[i + 1][j] + A[i][j] + S[i][j + 1] - S[i][j]);
      }
   }
   console.log(S[c + 1][d + 1] - S[a][d + 1] - S[c + 1][b] + S[a][b]);
});

hogeちゃんの画像

配列 A の要素数が N 行 M 列になりました。それ以外は【STEP: 5】と同じ。詳しくは【STEP: 1】の問題文中の（ヒント）をご参照下さい。

問題【FINAL】二次元累積和 7

Task

N✕M の二次元配列 A の長方形領域(左上 A_{a, b}, 右下 A_{c, d}) の累積和を求めてね。

【二次元累積和 7】コード

reader.on('close', () => {
   const [N, M, Q] = lines[0].split(' ').map(Number);
   const A = [];
   for (let i = 1; i < N + 1; i++) {
      A.push(lines[i].split(' ').map(Number));
   }
   const S = [
      []
   ];
   for (let i = 0; i <= M; i++) {
      S[0].push(0);
   }
   for (let i = 0; i < N; i++) {
      S.push([0]);
      for (let j = 0; j < M; j++) {
         S[i + 1].push(S[i + 1][j] + A[i][j] + S[i][j + 1] - S[i][j]);
      }
   }
   for (let i = N + 1; i < Q + N + 1; i++) {
      const [a, b, c, d] = lines[i].split(' ').map(Number);
      console.log(S[c + 1][d + 1] - S[a][d + 1] - S[c + 1][b] + S[a][b]);
   }
});

hogeちゃんの画像

総和を求める配列 A の長方形領域が Q 個になりました。

コメント