SparseTable2D
(src/data_structure/sparse_table_2d.hpp)

• View this file on GitHub
• Last update: 2024-11-09 01:34:39+09:00
• Include: #include "src/data_structure/sparse_table_2d.hpp"

SparseTable2D

冪等モノイド，つまり

• 結合則: $(a \cdot b) \cdot c = a \cdot (b \cdot c)$ for all $a, b, c \in S$
• 単位元の存在: $a \cdot e = e \cdot a = a$ for all $a \in S$
• 冪等性: $a \cdot a = a$ for all $a \in S$

を満たす代数構造に対し使用できるデータ構造です．

サイズ $N \times M$ の $S$ の二次元配列に対し，

• 長方形領域の要素の総積の取得

を $O(1)$ で行うことができます．

ただし，これは二項演算 op と単位元取得 e が定数時間で動くと仮定したときの計算量です．
これらが $O(f(n))$ かかる場合は，すべての計算量が $O(f(n))$ 倍となります．

また，要素を更新することはできません．

コンストラクタ

SparseTable2D<S, op, e> st(vector<vector<S>> v)

• 型 S
• 二項演算 S op(S a, S b)
• 単位元 S e()

を定義する必要があります．

例として，Range Minimum Queryなら，

int op(int a, int b) {
    return min(a, b);
}
int e() {
    return (int)1e9;
}
SparseTable2D<int, op, e> st(v);

のようになります．

• サイズ n * m = ssize(v) * ssize(v[0]) の二次元数列 a を作ります．
  v の内容が初期値となります．

計算量

• $O(nm \log (nm))$

prod

S st.prod(int lx, int rx, int ly, int ry)

op(a[lx][ly], a[lx][ly + 1], ..., a[lx][ry - 1], a[lx + 1][ly], ..., a[rx - 1][ry - 1]) を，冪等モノイドの性質を満たしていると仮定して返します．
$lx = rx$ または $ly = ry$ のときは e() を返します．

制約

• $0 \leq lx \leq rx \leq n$
• $0 \leq ly \leq ry \leq n$

計算量

• $O(1)$

Depends on

• template (src/template/template.hpp)

Verified with

• verify/unit_test/data_structure/sparse_table_2d.test.cpp

Code

#pragma once
#include "../template/template.hpp"
template <typename S, auto op, auto e>
struct SparseTable2D {
    SparseTable2D(const vector<vector<S>>& v)
        : h((int)v.size()), w((int)v[0].size()), LOG(max(h, w) + 1) {
        for(int i = 2; i < (int)LOG.size(); ++i) LOG[i] = LOG[i / 2] + 1;
        table = vector<vector<vector<vector<S>>>>(LOG[h] + 1, vector<vector<vector<S>>>(LOG[w] + 1, vector<vector<S>>(h, vector<S>(w, e()))));
        for(int i = 0; i < h; ++i) {
            for(int j = 0; j < w; ++j) {
                table[0][0][i][j] = v[i][j];
            }
        }
        for(int i = 0; i <= LOG[h]; ++i) {
            for(int j = 0; j <= LOG[w]; ++j) {
                for(int x = 0; x < h; ++x) {
                    for(int y = 0; y < w; ++y) {
                        if(i < LOG[h]) table[i + 1][j][x][y] = op(table[i][j][x][y], (x + (1 << i) < h) ? table[i][j][x + (1 << i)][y] : e());
                        if(j < LOG[w]) table[i][j + 1][x][y] = op(table[i][j][x][y], (y + (1 << j) < w) ? table[i][j][x][y + (1 << j)] : e());
                    }
                }
            }
        }
    }
    S prod(const int lx, const int rx, const int ly, const int ry) const {
        assert(0 <= lx and lx <= rx and rx <= h);
        assert(0 <= ly and ly <= ry and ry <= w);
        if(lx == rx or ly == ry) return e();
        const int kx = LOG[rx - lx];
        const int ky = LOG[ry - ly];
        return op(op(table[kx][ky][lx][ly], table[kx][ky][rx - (1 << kx)][ly]), op(table[kx][ky][lx][ry - (1 << ky)], table[kx][ky][rx - (1 << kx)][ry - (1 << ky)]));
    }

   private:
    int h, w;
    vector<vector<vector<vector<S>>>> table;
    vector<int> LOG;
};

#line 2 "src/template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long long, long long>;
#define rep(i, a, b) for(long long i = (a); i < (b); ++i)
#define rrep(i, a, b) for(long long i = (a); i >= (b); --i)
constexpr long long inf = 4e18;
struct SetupIO {
    SetupIO() {
        ios::sync_with_stdio(0);
        cin.tie(0);
        cout << fixed << setprecision(30);
    }
} setup_io;
#line 3 "src/data_structure/sparse_table_2d.hpp"
template <typename S, auto op, auto e>
struct SparseTable2D {
    SparseTable2D(const vector<vector<S>>& v)
        : h((int)v.size()), w((int)v[0].size()), LOG(max(h, w) + 1) {
        for(int i = 2; i < (int)LOG.size(); ++i) LOG[i] = LOG[i / 2] + 1;
        table = vector<vector<vector<vector<S>>>>(LOG[h] + 1, vector<vector<vector<S>>>(LOG[w] + 1, vector<vector<S>>(h, vector<S>(w, e()))));
        for(int i = 0; i < h; ++i) {
            for(int j = 0; j < w; ++j) {
                table[0][0][i][j] = v[i][j];
            }
        }
        for(int i = 0; i <= LOG[h]; ++i) {
            for(int j = 0; j <= LOG[w]; ++j) {
                for(int x = 0; x < h; ++x) {
                    for(int y = 0; y < w; ++y) {
                        if(i < LOG[h]) table[i + 1][j][x][y] = op(table[i][j][x][y], (x + (1 << i) < h) ? table[i][j][x + (1 << i)][y] : e());
                        if(j < LOG[w]) table[i][j + 1][x][y] = op(table[i][j][x][y], (y + (1 << j) < w) ? table[i][j][x][y + (1 << j)] : e());
                    }
                }
            }
        }
    }
    S prod(const int lx, const int rx, const int ly, const int ry) const {
        assert(0 <= lx and lx <= rx and rx <= h);
        assert(0 <= ly and ly <= ry and ry <= w);
        if(lx == rx or ly == ry) return e();
        const int kx = LOG[rx - lx];
        const int ky = LOG[ry - ly];
        return op(op(table[kx][ky][lx][ly], table[kx][ky][rx - (1 << kx)][ly]), op(table[kx][ky][lx][ry - (1 << ky)], table[kx][ky][rx - (1 << kx)][ry - (1 << ky)]));
    }

   private:
    int h, w;
    vector<vector<vector<vector<S>>>> table;
    vector<int> LOG;
};

Back to top page