Cumulative Sum 2D (二次元累積和) (dp/cumulative-sum-2d.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2026-08-10 06:35:14+00:00
Include: #include "dp/cumulative-sum-2d.hpp"

$2$ 次元の累積和です。事前に累積和を構築することで、矩形和を $O(1)$ で求められます。

コンストラクタ

CumulativeSum2D(int W, int H)

幅 W、高さ H の二次元配列で初期化します。各要素は $0$ です。

制約

$0 \leq W$
$0 \leq H$

計算量

$O(WH)$

add

void add(int x, int y, T z)

要素 $(x, y)$ に値 z を加えます。

制約

$0 \leq x \lt W$
$0 \leq y \lt H$
build より前に呼び出す

計算量

$O(1)$

build

void build()

累積和を構築します。

制約

add をすべて処理した後に1回だけ呼び出す

計算量

$O(WH)$

query

T query(int sx, int sy, int gx, int gy) const

半開矩形 $[sx, gx) \times [sy, gy)$ の要素の総和を返します。

制約

$0 \leq sx \leq gx \leq W$
$0 \leq sy \leq gy \leq H$
build を呼び出した後

計算量

$O(1)$

Verified with

test/verify/aoj-0560.test.cpp

Code

#pragma once

#include <vector>

template <class T>
struct CumulativeSum2D {
  std::vector<std::vector<T> > data;

  CumulativeSum2D(int W, int H) : data(W + 1, std::vector<T>(H + 1, 0)) {}

  void add(int x, int y, T z) {
    ++x, ++y;
    if (x >= data.size() || y >= data[0].size()) return;
    data[x][y] += z;
  }

  void build() {
    for (int i = 1; i < data.size(); i++) {
      for (int j = 1; j < data[i].size(); j++) {
        data[i][j] += data[i][j - 1] + data[i - 1][j] - data[i - 1][j - 1];
      }
    }
  }

  T query(int sx, int sy, int gx, int gy) const {
    return (data[gx][gy] - data[sx][gy] - data[gx][sy] + data[sx][sy]);
  }
};

#line 2 "dp/cumulative-sum-2d.hpp"

#include <vector>

template <class T>
struct CumulativeSum2D {
  std::vector<std::vector<T> > data;

  CumulativeSum2D(int W, int H) : data(W + 1, std::vector<T>(H + 1, 0)) {}

  void add(int x, int y, T z) {
    ++x, ++y;
    if (x >= data.size() || y >= data[0].size()) return;
    data[x][y] += z;
  }

  void build() {
    for (int i = 1; i < data.size(); i++) {
      for (int j = 1; j < data[i].size(); j++) {
        data[i][j] += data[i][j - 1] + data[i - 1][j] - data[i - 1][j - 1];
      }
    }
  }

  T query(int sx, int sy, int gx, int gy) const {
    return (data[gx][gy] - data[sx][gy] - data[gx][sy] + data[sx][sy]);
  }
};