This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub Harui-i/library
#include "dp/cumulative-sum-2d.hpp"
CumulativeSum2D< T >(int H, int W)
void add(int i, int j, T x)
座標 $(i,j)$に$x$を加算する。
void build()
二次元累積和を計算する。
T query(int si, int sj, int gi, int gj)
直積(?) $[si, gi) \times [sj, gj)の区間和を求める (0-indexed)。
build()
(だけどassertしてません。したほうがいいね)
#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]; } };