斜め累積和

斜め方向の累積和

斜め方向の累積和を以下の問題で使用した。今後も使いそうなので整理しておく。

atcoder.jp Submission #6315441 - Tenka1 Programmer Contest

実装例

cumの定義は第一引数を、第二引数をとして各斜め線のまでの累積和とした。

ll h, w;
cin >> h >> w;
vector<string> s(h);
REP(i, h) cin >> s[i];
vector<vector<ll>> cum(h+w+1, vector<ll>(w+1));
REP(ij, h+w) {
  REP(i, w) {
    int j = ij - i;
    if(j < 0 || h <= j ) {
      cum[ij][i+1] = cum[ij][i];
    }
    else if(s[j][i] == '.') {
      cum[ij][i+1] = cum[ij][i];
    }
    else {
      cum[ij][i+1] = cum[ij][i] + 1;
    }
  }
}
# ....
# ..$.
# .$..
# ....
# $で表される区間を取得したい場合は以下のように書く。
cout << cum[3][3] - cum[3][1] << endl;