Cumulative Sum 2D (二次元累積和)
(lib/data_structure/cumulative_sum_2d.hpp)

• View this file on GitHub
• Last update: 2024-11-18 03:25:02+09:00
• Include: #include "lib/data_structure/cumulative_sum_2d.hpp"

Cumulative Sum 2D (二次元累積和)

使い方

• CumulativeSum2D<T>(H, W): コンストラクタ
• add(x, y, z): (x, y) に z を加算します。
• imos(x1, y1, x2, y2, z): いもす法において、[(x1, y1), (x2, y2)) に v を加算します。
• build(): 加算された配列を構築します。
• sum(x1, y1, x2, y2): [(x1, y1), (x2, y2)) の和を取得します。

計算量

• CumulativeSum2D<T>(H, W): $\mathrm{O}(HW)$
• add(x, y, z): $\mathrm{O}(1)$
• imos(x1, y1, x2, y2, z): $\mathrm{O}(1)$
• build(): $\mathrm{O}(HW)$
• sum(x1, y1, x2, y2): $\mathrm{O}(1)$

Verified with

• test/aoj/dsl/dsl_5_b_cs2d.test.cpp

Code

#pragma once

/**
 * @brief Cumulative Sum 2D (二次元累積和)
 * @docs docs/data_structure/cumulative_sum_2d.md
 */

#include <vector>
#include <cassert>

template <typename T>
struct CumulativeSum2D{
    int H, W;
    std::vector<std::vector<T>> data;

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

    void add(int i, int j, const T &z){
        ++i, ++j;
        if(i >= (int) data.size() || j >= (int) data[0].size()) return;
        data[i][j] += z;
    }

    void imos(const int i1, const int j1, const int i2, const int j2, const T &z = 1) {
        assert(0 <= i1 && i1 <= i2 && i2 <= H);
        assert(0 <= j1 && j1 <= j2 && j2 <= W);
        add(i1, j1, z);
        add(i1, j2, -z);
        add(i2, j1, -z);
        add(i2, j2, z);
    }

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

    inline T imos_get(const int i, const int j) const{
        return data[i + 1][j + 1];
    }

    inline T sum(const int i1, const int j1, const int i2, const int j2) const {
        assert(0 <= i1 && i1 <= i2 && i2 <= H);
        assert(0 <= j1 && j1 <= j2 && j2 <= W);
        return (data[i2][j2] - data[i1][j2] - data[i2][j1] + data[i1][j1]);
    }
};

#line 2 "lib/data_structure/cumulative_sum_2d.hpp"

/**
 * @brief Cumulative Sum 2D (二次元累積和)
 * @docs docs/data_structure/cumulative_sum_2d.md
 */

#include <vector>
#include <cassert>

template <typename T>
struct CumulativeSum2D{
    int H, W;
    std::vector<std::vector<T>> data;

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

    void add(int i, int j, const T &z){
        ++i, ++j;
        if(i >= (int) data.size() || j >= (int) data[0].size()) return;
        data[i][j] += z;
    }

    void imos(const int i1, const int j1, const int i2, const int j2, const T &z = 1) {
        assert(0 <= i1 && i1 <= i2 && i2 <= H);
        assert(0 <= j1 && j1 <= j2 && j2 <= W);
        add(i1, j1, z);
        add(i1, j2, -z);
        add(i2, j1, -z);
        add(i2, j2, z);
    }

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

    inline T imos_get(const int i, const int j) const{
        return data[i + 1][j + 1];
    }

    inline T sum(const int i1, const int j1, const int i2, const int j2) const {
        assert(0 <= i1 && i1 <= i2 && i2 <= H);
        assert(0 <= j1 && j1 <= j2 && j2 <= W);
        return (data[i2][j2] - data[i1][j2] - data[i2][j1] + data[i1][j1]);
    }
};

Back to top page