sparse table
(include/emthrm/data_structure/sparse_table.hpp)

• View this file on GitHub
• Last update: 2023-02-23 21:59:12+09:00
• Include: #include "emthrm/data_structure/sparse_table.hpp"

時間計算量

$\langle O(N\log{N}), O(1) \rangle$

仕様

template <typename Band>
struct SparseTable;

• Band：帯である要素型

メンバ変数

名前	効果・戻り値
SparseTable();	デフォルトコンストラクタ
explicit SparseTable(const std::vector<Band>& a, const BinOp bin_op);	$A$ に対して二項演算 $\mathrm{binOp}$ のオブジェクトを構築する。
void init(const std::vector<Band>& a, const BinOp bin_op_);	$A$ によって初期化する。
Band query(const int left, const int right) const;	$[\mathrm{left}, \mathrm{right})$ における演算を行った解

メンバ型

名前	効果・戻り値
BinOp	std::function<Band(Band, Band)>

参考文献

• Michael A. Bender and Martín Farach-Colton: The LCA Problem Revisited, LATIN 2000: Theoretical Informatics, pp. 88–94 (2000). https://doi.org/10.1007/10719839_9
• http://tookunn.hatenablog.com/entry/2016/07/13/211148
• https://github.com/drken1215/algorithm/blob/0db023d94ca9c79a24ef13f5905e6bab056bdafe/DataStructure/sparse_table.cpp

Submissons

https://judge.yosupo.jp/submission/2719

Required by

• 最小共通祖先 (lowest common ancestor) Euler tour technique 版 (include/emthrm/graph/tree/lowest_common_ancestor_by_euler_tour_technique.hpp)
• longest common prefix (include/emthrm/string/longest_common_prefix.hpp)

Verified with

• データ構造/sparse table (test/data_structure/sparse_table.test.cpp)
• グラフ/木/最小共通祖先 Euler tour technique 版 (test/graph/tree/lowest_common_ancestor_by_euler_tour.test.cpp)
• 文字列/longest common prefix (test/string/longest_common_prefix.test.cpp)

Code

#ifndef EMTHRM_DATA_STRUCTURE_SPARSE_TABLE_HPP_
#define EMTHRM_DATA_STRUCTURE_SPARSE_TABLE_HPP_

#include <algorithm>
#include <bit>
#include <cassert>
#include <functional>
#include <vector>

namespace emthrm {

template <typename Band>
struct SparseTable {
  using BinOp = std::function<Band(Band, Band)>;

  SparseTable() = default;

  explicit SparseTable(const std::vector<Band>& a, const BinOp bin_op) {
    init(a, bin_op);
  }

  void init(const std::vector<Band>& a, const BinOp bin_op_) {
    bin_op = bin_op_;
    const int n = a.size();
    assert(n > 0);
    lg.assign(n + 1, 0);
    for (int i = 2; i <= n; ++i) {
      lg[i] = lg[i >> 1] + 1;
    }
    const int table_h = std::countr_zero(std::bit_floor(a.size())) + 1;
    data.assign(table_h, std::vector<Band>(n));
    std::copy(a.begin(), a.end(), data.front().begin());
    for (int i = 1; i < table_h; ++i) {
      for (int j = 0; j + (1 << i) <= n; ++j) {
        data[i][j] = bin_op(data[i - 1][j], data[i - 1][j + (1 << (i - 1))]);
      }
    }
  }

  Band query(const int left, const int right) const {
    assert(left < right);
    const int h = lg[right - left];
    return bin_op(data[h][left], data[h][right - (1 << h)]);
  }

 private:
  BinOp bin_op;
  std::vector<int> lg;
  std::vector<std::vector<Band>> data;
};

}  // namespace emthrm

#endif  // EMTHRM_DATA_STRUCTURE_SPARSE_TABLE_HPP_

#line 1 "include/emthrm/data_structure/sparse_table.hpp"



#include <algorithm>
#include <bit>
#include <cassert>
#include <functional>
#include <vector>

namespace emthrm {

template <typename Band>
struct SparseTable {
  using BinOp = std::function<Band(Band, Band)>;

  SparseTable() = default;

  explicit SparseTable(const std::vector<Band>& a, const BinOp bin_op) {
    init(a, bin_op);
  }

  void init(const std::vector<Band>& a, const BinOp bin_op_) {
    bin_op = bin_op_;
    const int n = a.size();
    assert(n > 0);
    lg.assign(n + 1, 0);
    for (int i = 2; i <= n; ++i) {
      lg[i] = lg[i >> 1] + 1;
    }
    const int table_h = std::countr_zero(std::bit_floor(a.size())) + 1;
    data.assign(table_h, std::vector<Band>(n));
    std::copy(a.begin(), a.end(), data.front().begin());
    for (int i = 1; i < table_h; ++i) {
      for (int j = 0; j + (1 << i) <= n; ++j) {
        data[i][j] = bin_op(data[i - 1][j], data[i - 1][j + (1 << (i - 1))]);
      }
    }
  }

  Band query(const int left, const int right) const {
    assert(left < right);
    const int h = lg[right - left];
    return bin_op(data[h][left], data[h][right - (1 << h)]);
  }

 private:
  BinOp bin_op;
  std::vector<int> lg;
  std::vector<std::vector<Band>> data;
};

}  // namespace emthrm

Back to top page