二维差分

发表于 分类于 ， 阅读次数： 本文字数： 340 阅读时长 ≈ 1 分钟 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
auto insert = [&](i64 x1, i64 y1, i64 x2, i64 y2, i64 c,
                  vector<vector<i64>> &b) {
  b[x1][y1] += c;
  b[x2 + 1][y1] -= c;
  b[x1][y2 + 1] -= c;
  b[x2 + 1][y2 + 1] += c;
};

auto TD_prefix_and = [&](vector<vector<i64>> &b) {
  for (int i = 1; i < n; i++)
    for (int j = 1; j < n; j++)
      b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];
};