トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

二次元累積和

[アルゴリズム]

練習のための問題は 競技プログラミングの履歴

imos法・累積和 を書いているので、それも参考にどうぞ。

累積和

   累積の和をとっておくと、区間の総和がO(1)で取得できる 参考
   二次元に拡張することもできる

  詳しい解説 with C++

// This file is a "Hello, world!" in C++ language by GCC for wandbox.
#include <iostream>
#include <algorithm>

#define rep(i,n) for(int i=0;i<n;i++)

template <class T>
std::vector<std::vector<T>> imos_2d(const std::vector<std::vector<T>>& a) {
    int h = a.size(), w = a[0].size();
    std::vector<std::vector<T>> s(h + 1, std::vector<T>(w + 1, 0));
    rep(i, h) rep(j, w) s[i + 1][j + 1] = a[i][j];
    rep(i, h + 1) rep(j, w) s[i][j + 1] += s[i][j];
    rep(i, h) rep(j, w + 1) s[i + 1][j] += s[i][j];
    
    std::cout << "array s is like following:" << std::endl;
    
    for (int i = 0; i < h+1; i++) {
        for (int j = 0; j < w+1; j++) {
            if (j!=w) {
                std::cout << s[i][j] << ", ";
            } else {
                std::cout << s[i][j];
            }
        }
        std::cout << "" << std::endl;
    }
    
    return s;
}

template <class T>
int sum(const std::vector<std::vector<T>>& s, int i, int j, int h, int w) {
    return s[i + h][j + w] - s[i][j + w] + s[i][j] - s[i + h][j];
}

int main()
{   
    std::vector<std::vector<int>> a = {
        {0,1,1,0,1},
        {1,0,0,1,1},
        {0,1,0,1,0},
        {0,0,0,1,0},
        {1,0,0,0,1}
    };
        
    auto s = imos_2d(a);
    std::cout << sum(s,2,1,3,3) << std::endl;
}
  • 出力
    • 合計値が正しく出た
array s is like following:
0, 0, 0, 0, 0, 0
0, 0, 1, 2, 2, 3
0, 1, 2, 3, 4, 6
0, 1, 3, 4, 6, 8
0, 1, 3, 4, 7, 9
0, 2, 4, 5, 8, 11
3

  アルゴリズム with Ruby

def imos_2d(a)
  h,w = a.length,a.first.length
  s = Array.new(h+1).map{Array.new(w+1,0)}
  for i in 0...h
    for j in 0...w
      s[i+1][j+1] = a[i][j]
    end
  end
  for i in 0...h+1
    for j in 0...w
      s[i][j+1] += s[i][j]
    end
  end
  for i in 0...h
    for j in 0...w+1
      s[i+1][j] += s[i][j]
    end
  end
  s
end

def sum(s,i,j,h,w)
  s[i+h][j+w] - s[i][j+w] + s[i][j] - s[i+h][j]
end

a = Array.new(5).map{Array.new(5,0)}
a = [ [0,1,1,0,1], [1,0,0,1,1], [0,1,0,1,0], [0,0,0,1,0], [1,0,0,0,1] ];

s = imos_2d(a)
s.each{|r| p r}

puts sum(s,2,1,3,3)
お名前: コメント: