disjoint sparse table
(include/emthrm/data_structure/disjoint_sparse_table.hpp)

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

時間計算量

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

仕様

template <typename Semigroup, typename BinOp>
struct DisjointSparseTable;

• Semigroup：半群である要素型
• BinOp：二項演算を表す型

メンバ関数

名前	効果・戻り値
explicit DisjointSparseTable(const std::vector<Semigroup>& a, const BinOp bin_op = BinOp());	$A$ に対して二項演算 $\mathrm{binOp}$ のオブジェクトを構築する。
Semigroup query(const int left, int right) const;	$\lbrack \mathrm{left}, \mathrm{right})$ における演算を行った解

参考文献

• http://noshi91.hatenablog.com/entry/2018/05/08/183946
• https://github.com/drken1215/algorithm/blob/f65b8a3b2603f5efb10a8a912c2403b404c29813/DataStructure/disjoint_sparse_table.cpp

TODO

• sqrt-tree
  • https://codeforces.com/blog/entry/57046
  • https://qiita.com/sotanishy/items/89f4dd452bcddd332f24
  • https://cp-algorithms.com/data_structures/sqrt-tree.html
  • https://qiita.com/sotanishy/items/89f4dd452bcddd332f24
  • https://sotanishy.github.io/cp-library-cpp/data-structure/sqrt_tree.cpp
• 木上の disjoint sparse table
  • https://noshi91.hatenablog.com/entry/2023/12/05/033518

Submissons

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

Verified with

• データ構造/disjoint sparse table (test/data_structure/disjoint_sparse_table.test.cpp)

Code

#ifndef EMTHRM_DATA_STRUCTURE_DISJOINT_SPARSE_TABLE_HPP_
#define EMTHRM_DATA_STRUCTURE_DISJOINT_SPARSE_TABLE_HPP_

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

namespace emthrm {

template <typename Semigroup, typename BinOp>
struct DisjointSparseTable {
  explicit DisjointSparseTable(const std::vector<Semigroup>& a,
                               const BinOp bin_op = BinOp())
      : bin_op(bin_op) {
    const int table_h = std::max(std::countr_zero(std::bit_ceil(a.size())), 1);
    lg.assign(1 << table_h, 0);
    for (int i = 2; i < (1 << table_h); ++i) {
      lg[i] = lg[i >> 1] + 1;
    }
    const int n = a.size();
    data.assign(table_h, std::vector<Semigroup>(n));
    std::copy(a.begin(), a.end(), data.front().begin());
    for (int i = 1; i < table_h; ++i) {
      const int shift = 1 << i;
      for (int left = 0; left < n; left += shift << 1) {
        const int mid = std::min(left + shift, n);
        data[i][mid - 1] = a[mid - 1];
        for (int j = mid - 2; j >= left; --j) {
          data[i][j] = bin_op(a[j], data[i][j + 1]);
        }
        if (n <= mid) break;
        const int right = std::min(mid + shift, n);
        data[i][mid] = a[mid];
        for (int j = mid + 1; j < right; ++j) {
          data[i][j] = bin_op(data[i][j - 1], a[j]);
        }
      }
    }
  }

  Semigroup query(const int left, int right) const {
    assert(left < right);
    if (left == --right) return data[0][left];
    const int h = lg[left ^ right];
    return bin_op(data[h][left], data[h][right]);
  }

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

}  // namespace emthrm

#endif  // EMTHRM_DATA_STRUCTURE_DISJOINT_SPARSE_TABLE_HPP_

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



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

namespace emthrm {

template <typename Semigroup, typename BinOp>
struct DisjointSparseTable {
  explicit DisjointSparseTable(const std::vector<Semigroup>& a,
                               const BinOp bin_op = BinOp())
      : bin_op(bin_op) {
    const int table_h = std::max(std::countr_zero(std::bit_ceil(a.size())), 1);
    lg.assign(1 << table_h, 0);
    for (int i = 2; i < (1 << table_h); ++i) {
      lg[i] = lg[i >> 1] + 1;
    }
    const int n = a.size();
    data.assign(table_h, std::vector<Semigroup>(n));
    std::copy(a.begin(), a.end(), data.front().begin());
    for (int i = 1; i < table_h; ++i) {
      const int shift = 1 << i;
      for (int left = 0; left < n; left += shift << 1) {
        const int mid = std::min(left + shift, n);
        data[i][mid - 1] = a[mid - 1];
        for (int j = mid - 2; j >= left; --j) {
          data[i][j] = bin_op(a[j], data[i][j + 1]);
        }
        if (n <= mid) break;
        const int right = std::min(mid + shift, n);
        data[i][mid] = a[mid];
        for (int j = mid + 1; j < right; ++j) {
          data[i][j] = bin_op(data[i][j - 1], a[j]);
        }
      }
    }
  }

  Semigroup query(const int left, int right) const {
    assert(left < right);
    if (left == --right) return data[0][left];
    const int h = lg[left ^ right];
    return bin_op(data[h][left], data[h][right]);
  }

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

}  // namespace emthrm

Back to top page