2次元累積和
(DataStructure/CumulativeSum2D.hpp)

• View this file on GitHub
• Last update: 2023-12-31 10:41:43+09:00
• Include: #include "DataStructure/CumulativeSum2D.hpp"

概要

平面内にある値の総和を収得できるデータ構造。

関数名など	機能	計算量
(1) CumulativeSum2D<T>(int H, int W) (2) CumulativeSum2D(std::vector<std::vector<T>> A)	+ と - が定義されている構造体を載せることができる。 (1) $H \times W$ の配列を初期値 $0$ で作成する。 (2) 2次元 vector に基づく値で 2次元累積和を構成する。	$\text{O}(HW)$
void add(int y, int x, T z)	a[y][x] += z を行う. $0 \leq y < H$, $0 \leq x < W$	$\text{O}(1)$
void build()	二次元累積和を構築する。コントラクタに2次元vectorを渡した場合は不要。	$\text{O}(HW)$
T query(int ly, int lx, int ry, int rx)	・ $ly \leq y < ry$ ・ $lx \leq x < rx$ を満たす a[y][x] の値の総和を収得する。	$\text{O}(1)$

Verified with

• Test/Aizu Online Judge/ALDS1/ALDS1_14_C.test.cpp
• Test/yukicoder/yuki0755.test.cpp

Code

template <class T> struct CumulativeSum2D{
    int h, w;
    std::vector<std::vector<T>> dat;
    CumulativeSum2D(int H, int W) : h(H), w(W), dat(H + 1, std::vector<T>(W + 1, 0)) {}
    CumulativeSum2D(std::vector<std::vector<T>> &A) 
        : h(A.size()), w(A[0].size()), dat(h + 1, std::vector<T>(w + 1, 0)) {
        for(int y = 1; y <= h; y++){
            for(int x = 1; x <= w; x++){
                dat[y][x] = A[y - 1][x - 1] + dat[y][x - 1] + dat[y - 1][x] - dat[y - 1][x - 1];
            }
        }
    }
    void add(int y, int x, T z){
        assert(0 <= y && y < h);
        assert(0 <= x && x < w);
        dat[y + 1][x + 1] += z;
    }
    void build(){
        for(int y = 1; y <= h; y++) {
            for(int x = 1; x <= w; x++) {
                dat[y][x] += dat[y][x - 1] + dat[y - 1][x] - dat[y - 1][x - 1];
            }
        }
    }
    T query(int ly, int lx, int ry, int rx){
        assert(0 <= ly && ly <= ry && ry <= h);
        assert(0 <= lx && lx <= rx && rx <= w);
        return dat[ry][rx] - dat[ly][rx] - dat[ry][lx] + dat[ly][lx];
    }
};

#line 1 "DataStructure/CumulativeSum2D.hpp"
template <class T> struct CumulativeSum2D{
    int h, w;
    std::vector<std::vector<T>> dat;
    CumulativeSum2D(int H, int W) : h(H), w(W), dat(H + 1, std::vector<T>(W + 1, 0)) {}
    CumulativeSum2D(std::vector<std::vector<T>> &A) 
        : h(A.size()), w(A[0].size()), dat(h + 1, std::vector<T>(w + 1, 0)) {
        for(int y = 1; y <= h; y++){
            for(int x = 1; x <= w; x++){
                dat[y][x] = A[y - 1][x - 1] + dat[y][x - 1] + dat[y - 1][x] - dat[y - 1][x - 1];
            }
        }
    }
    void add(int y, int x, T z){
        assert(0 <= y && y < h);
        assert(0 <= x && x < w);
        dat[y + 1][x + 1] += z;
    }
    void build(){
        for(int y = 1; y <= h; y++) {
            for(int x = 1; x <= w; x++) {
                dat[y][x] += dat[y][x - 1] + dat[y - 1][x] - dat[y - 1][x - 1];
            }
        }
    }
    T query(int ly, int lx, int ry, int rx){
        assert(0 <= ly && ly <= ry && ry <= h);
        assert(0 <= lx && lx <= rx && rx <= w);
        return dat[ry][rx] - dat[ly][rx] - dat[ry][lx] + dat[ly][lx];
    }
};

Back to top page