src/DataStructure/Imos2D.hpp

View this file on GitHub
Last update: 2020-05-19 02:16:10+09:00
Include: #include "src/DataStructure/Imos2D.hpp"

概要

H*Wの二次元データで長方形部分に区間加算するクエリをimos法によって行う。各クエリO(1)、構築にO(HW)。

imos法: https://imoz.jp/algorithms/imos_method.html
多次元の累積和についてはこれがわかりやすい: https://qiita.com/convexineq/items/afc84dfb9ee4ec4a67d5

Code

/// @docs src/DataStructure/Imos2D.md
// 0-indexed
// t.add(i0, j0, i1, j1) -> t.run() -> t[i][j]
template <class T> struct Imos2D {
    int n, m;
    std::vector<std::vector<T>> t;  // 0-indexed!!, -x分のために配列の外側を1大きめに
    Imos2D(int n_, int m_) : n(n_), m(m_), t(n_ + 1, std::vector<T>(m_ + 1)) {}
    // i0 <= i < i1, j0 < j < j1の範囲に+x
    void add(int i0, int j0, int i1, int j1, T x) {
        t[i0][j0] += x, t[i1][j1] += x;
        t[i1][j0] -= x, t[i0][j1] -= x;
    }
    // 2方向に累積和をとる
    void build() {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) t[i + 1][j] += t[i][j];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) t[i][j + 1] += t[i][j];
    }
    std::vector<T>& operator[](int i) { return t[i]; }
};

#line 1 "src/DataStructure/Imos2D.hpp"
/// @docs src/DataStructure/Imos2D.md
// 0-indexed
// t.add(i0, j0, i1, j1) -> t.run() -> t[i][j]
template <class T> struct Imos2D {
    int n, m;
    std::vector<std::vector<T>> t;  // 0-indexed!!, -x分のために配列の外側を1大きめに
    Imos2D(int n_, int m_) : n(n_), m(m_), t(n_ + 1, std::vector<T>(m_ + 1)) {}
    // i0 <= i < i1, j0 < j < j1の範囲に+x
    void add(int i0, int j0, int i1, int j1, T x) {
        t[i0][j0] += x, t[i1][j1] += x;
        t[i1][j0] -= x, t[i0][j1] -= x;
    }
    // 2方向に累積和をとる
    void build() {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) t[i + 1][j] += t[i][j];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) t[i][j + 1] += t[i][j];
    }
    std::vector<T>& operator[](int i) { return t[i]; }
};