いもす法とは

階差を累積和の性質を利用して、配列のある範囲において同一処理をする際に活用できる手法である。配列に対する処理を階差に対して行い、処理後に階差の累積和を取ることで結果を得ることができる。

一次元いもす法

例題

典型90問064 - Uplift（★3）

ここでは例題の設定で、全地殻変動後の各区画の標高を求めてみよう。

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define rep(i, n) for (int i = 0; i < (n); ++i)

int main() {
  int N, Q; cin >> N >> Q;
  vi A(N+1), B(N);
  A[0] = 0;
  for (int i = 1; i <= N; i++) cin >> A[i];
  rep(i, N+1) B[i] = A[i+1] - A[i]; // 階差配列を作成
  
  rep(qi, Q) {
    int L, R, V; cin >> L >> R >> V;
    B[L-1] += V; B[R] -= V;
  }
  for (int i = 1; i < N; i++) B[i] += B[i-1]; // 累積和を取る
  
  rep(i, N) cout << B[i] << ' ';
  cout << endl;
}

二次元いもす法

例題

典型90問028 - Cluttered Paper（★4）

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define rep(i, n) for (int i = 0; i < (n); ++i)

int main() {
  int N; cin >> N;
  const int M = 1002;
  vector<vi> A(M, vi(M, 0)); // 階差配列として扱う
  rep(i, N) {
    // 左上の座標(lx. ly)、右下の座標(rx, ry)
    int lx, ly, rx, ry;
    cin >> lx >> ly >> rx >> ry;
    A[lx][ly]++; A[rx][ry]++;
    A[rx][ly]--; A[lx][ry]--;
  }
  
  rep(i, M) rep(j, M-1) A[i][j+1] += A[i][j]; // 行ごとに累積和を取る
  rep(j, M) rep(i, M-1) A[i+1][j] += A[i][j]; // 列ごとに累積和を取る
  
  vi ans(N+1, 0);
  rep(i, M-1) rep(j, M-1) ans[A[i][j]]++;
  for (int i = 1; i <= N; i++) cout << ans[i] << endl;
}

一次元いもす法から二次元いもす法の拡張が理解できれば、三次元いもす法も同様である。

間違っている箇所や補足説明などがありましたら、ご指摘いただけますと幸いです。