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

• View this file on GitHub
• Last update: 2024-08-11 15:34:25+09:00
• Include: #include "dp/cumulative-sum-2d.hpp"
• Link: https://ngtkana.hatenablog.com/entry/2023/12/04/194327

コンストラクタ

CumulativeSum2D< T >(int H, int W)

1. サイズ$H$ * $W$ の二次元グリッドを作成する。

計算量

• $O(1)$

add

void add(int i, int j, T x)

座標 $(i,j)$に$x$を加算する。

制約

• $0 \leq i \lt H, 0 \leq j \lt W $ (だけどassertしてません。したほうがいいね)

計算量

• O(1)

build

void build()

二次元累積和を計算する。

計算量

• $O(1)$

query

T query(int si, int sj, int gi, int gj)

直積(?) $[si, gi) \times [sj, gj)の区間和を求める (0-indexed)。

制約

• $0 \leq si \lt H $
• $0 \leq sj \lt W $
• $0 \leq gi \leq H $
• $0 \leq gj \leq W $
• build()が呼ばれた後に呼ばれる必要がある

(だけどassertしてません。したほうがいいね)

計算量

• $O(1)$

Verified with

• test/verify/aoj-0560.test.cpp

Code

#ifndef HARUILIB_DP_CUMULATIVE_SUM_2D_HPP
#define HARUILIB_DP_CUMULATIVE_SUM_2D_HPP

#include <cassert>
#include <vector>

template<class T>
struct CumulativeSum2D {
  bool has_built = false;
  int H, W;
  std::vector<std::vector<T>> data;

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

  void add (int i, int j, T x) {
    assert(0 <= i && i < H && 0 <= j && j < W && !has_built);
    data[i+1][j+1] += x;
  }

  // https://ngtkana.hatenablog.com/entry/2023/12/04/194327
  // 1B
  void build() {
    assert(!has_built);
    for (int i=1; i<=H; i++) {
      for (int j=1; j<=W; j++) {
        data[i][j] += data[i-1][j];
      }
    }

    for (int i=1; i<=H; i++) {
      for (int j=1; j<=W; j++) {
        data[i][j] += data[i][j-1];
      }
    }


    has_built = true;
  }

  // [si, gi) * [sj, gj)
  T query(int si, int sj, int gi, int gj) {
    assert(has_built);
    assert(0 <= si && si < H && 0 <= sj && sj < W);
    assert(0 <= gi && gi <= H && 0 <= gj && gj <= W);
    assert(si <= gi && sj <= gj);
    return data[gi][gj] - data[si][gj] - data[gi][sj] + data[si][sj];
  }
};
#endif //HARUILIB_DP_CUMULATIVE_SUM_2D_HPP

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



#include <cassert>
#include <vector>

template<class T>
struct CumulativeSum2D {
  bool has_built = false;
  int H, W;
  std::vector<std::vector<T>> data;

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

  void add (int i, int j, T x) {
    assert(0 <= i && i < H && 0 <= j && j < W && !has_built);
    data[i+1][j+1] += x;
  }

  // https://ngtkana.hatenablog.com/entry/2023/12/04/194327
  // 1B
  void build() {
    assert(!has_built);
    for (int i=1; i<=H; i++) {
      for (int j=1; j<=W; j++) {
        data[i][j] += data[i-1][j];
      }
    }

    for (int i=1; i<=H; i++) {
      for (int j=1; j<=W; j++) {
        data[i][j] += data[i][j-1];
      }
    }


    has_built = true;
  }

  // [si, gi) * [sj, gj)
  T query(int si, int sj, int gi, int gj) {
    assert(has_built);
    assert(0 <= si && si < H && 0 <= sj && sj < W);
    assert(0 <= gi && gi <= H && 0 <= gj && gj <= W);
    assert(si <= gi && sj <= gj);
    return data[gi][gj] - data[si][gj] - data[gi][sj] + data[si][sj];
  }
};

Back to top page