平方分割 (sqrt decomposition)
(include/emthrm/misc/sqrt_decomposition.hpp)

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

時間計算量

$\langle O(N), O(\sqrt{N}) \rangle$

仕様

struct SqrtDecomposition;

メンバ変数

名前	説明
const int block_size	ブロックのサイズ
const int n	ブロックの数
std::vector<int> ls std::vector<int> rs	[ls[i], rs[i]) はブロック $i$ に対応する列のインデックス
std::vector<bool> to_be_eval	ブロックを評価すべきか。

メンバ関数

名前	効果・戻り値	備考
explicit SqrtDecomposition(const int n_);	サイズ $N$ のオブジェクトを構築する。
template <typename T> void partial_update(const int idx, const T val);	$\mathrm{val}$ を基に $A_{\mathrm{idx}}$ を更新する。	関数プロトタイプ
template <typename T> void total_update(const int idx, const T val);	$\mathrm{val}$ を基にブロック $\mathrm{idx}$ を更新する。	関数プロトタイプ
template <typename T> void update(const int l, const int r, const T val);	$\mathrm{val}$ を基に $\lbrack l, r)$ を更新する。
template <typename T> void partial_query(const int idx, T* val);	$A_{\mathrm{idx}}$ を基にクエリの解 $\mathrm{val}$ を更新する。	関数プロトタイプ
template <typename T> void total_query(const int idx, T* val);	ブロック $\mathrm{idx}$ を基にクエリの解 $\mathrm{val}$ を更新する。	関数プロトタイプ
template <typename T> T query(const int l, const int r, const T id);	$\lbrack l, r)$ に対するクエリの解	$\mathrm{id}$ は単位元である。

参考文献

• https://twitter.com/chokudai/status/1125634200084729857

TODO

• https://www.hamayanhamayan.com/entry/2017/04/12/180257
• 指定された頂点たちの最小共通祖先関係を保って木を圧縮してできる補助的な木
  • https://noshi91.github.io/algorithm-encyclopedia/auxiliary-tree
  • https://www.slideshare.net/iwiwi/2-12188845/7
  • http://drken1215.hatenablog.com/entry/2018/08/14/193500
  • https://sotanishy.github.io/cp-library-cpp/tree/auxiliary_tree.cpp
  • 問題例 “Preserve Connectivity”
  • 問題例 “Leaf Color”
• 木の平方分割
  • http://topcoder.g.hatena.ne.jp/iwiwi/20111205/1323099376
  • https://tubo28.me/compprog/algorithm/sqrt-decomp-tree/
  • http://noshi91.hatenablog.com/entry/2019/12/07/140433

Submissons

https://onlinejudge.u-aizu.ac.jp/solutions/problem/DSL_2_G/review/4087985/emthrm/C++14

Verified with

• その他/平方分割 (test/misc/sqrt_decomposition.test.cpp)

Code

#ifndef EMTHRM_MISC_SQRT_DECOMPOSITION_HPP_
#define EMTHRM_MISC_SQRT_DECOMPOSITION_HPP_

#include <cmath>
#include <vector>

namespace emthrm {

struct SqrtDecomposition {
  const int block_size, n;
  std::vector<int> ls, rs;
  std::vector<bool> to_be_eval;

  explicit SqrtDecomposition(const int n_)
      : block_size(std::round(std::sqrt(n_))),
        n((n_ + block_size - 1) / block_size) {
    ls.resize(n);
    rs.resize(n);
    to_be_eval.assign(n, false);
    for (int i = 0; i < n; ++i) {
      ls[i] = block_size * i;
      rs[i] = (i + 1 == n ? n_ : block_size * (i + 1));
    }
  }

  template <typename T> void partial_update(const int idx, const T val);

  template <typename T> void total_update(const int idx, const T val);

  template <typename T>
  void update(const int l, const int r, const T val) {
    if (r <= l) [[unlikely]] return;
    const int b_l = l / block_size, b_r = (r - 1) / block_size;
    if (b_l < b_r) {
      if (l == ls[b_l]) {
        total_update(b_l, val);
      } else {
        for (int i = l; i < rs[b_l]; ++i) {
          partial_update(i, val);
        }
      }
      for (int i = b_l + 1; i < b_r; ++i) {
        total_update(i, val);
      }
      if (r == rs[b_r]) {
        total_update(b_r, val);
      } else {
        for (int i = ls[b_r]; i < r; ++i) {
          partial_update(i, val);
        }
      }
    } else {
      for (int i = l; i < r; ++i) {
        partial_update(i, val);
      }
    }
  }

  template <typename T> void partial_query(const int idx, T* val);

  template <typename T> void total_query(const int idx, T* val);

  template <typename T>
  T query(const int l, const int r, const T id) {
    const int b_l = l / block_size, b_r = (r - 1) / block_size;
    T res = id;
    if (b_l < b_r) {
      if (l == ls[b_l]) {
        total_query(b_l, &res);
      } else {
        for (int i = l; i < rs[b_l]; ++i) {
          partial_query(i, &res);
        }
      }
      for (int i = b_l + 1; i < b_r; ++i) {
        total_query(i, &res);
      }
      if (r == rs[b_r]) {
        total_query(b_r, &res);
      } else {
        for (int i = ls[b_r]; i < r; ++i) {
          partial_query(i, &res);
        }
      }
    } else {
      for (int i = l; i < r; ++i) {
        partial_query(i, &res);
      }
    }
    return res;
  }
};

}  // namespace emthrm

#endif  // EMTHRM_MISC_SQRT_DECOMPOSITION_HPP_

#line 1 "include/emthrm/misc/sqrt_decomposition.hpp"



#include <cmath>
#include <vector>

namespace emthrm {

struct SqrtDecomposition {
  const int block_size, n;
  std::vector<int> ls, rs;
  std::vector<bool> to_be_eval;

  explicit SqrtDecomposition(const int n_)
      : block_size(std::round(std::sqrt(n_))),
        n((n_ + block_size - 1) / block_size) {
    ls.resize(n);
    rs.resize(n);
    to_be_eval.assign(n, false);
    for (int i = 0; i < n; ++i) {
      ls[i] = block_size * i;
      rs[i] = (i + 1 == n ? n_ : block_size * (i + 1));
    }
  }

  template <typename T> void partial_update(const int idx, const T val);

  template <typename T> void total_update(const int idx, const T val);

  template <typename T>
  void update(const int l, const int r, const T val) {
    if (r <= l) [[unlikely]] return;
    const int b_l = l / block_size, b_r = (r - 1) / block_size;
    if (b_l < b_r) {
      if (l == ls[b_l]) {
        total_update(b_l, val);
      } else {
        for (int i = l; i < rs[b_l]; ++i) {
          partial_update(i, val);
        }
      }
      for (int i = b_l + 1; i < b_r; ++i) {
        total_update(i, val);
      }
      if (r == rs[b_r]) {
        total_update(b_r, val);
      } else {
        for (int i = ls[b_r]; i < r; ++i) {
          partial_update(i, val);
        }
      }
    } else {
      for (int i = l; i < r; ++i) {
        partial_update(i, val);
      }
    }
  }

  template <typename T> void partial_query(const int idx, T* val);

  template <typename T> void total_query(const int idx, T* val);

  template <typename T>
  T query(const int l, const int r, const T id) {
    const int b_l = l / block_size, b_r = (r - 1) / block_size;
    T res = id;
    if (b_l < b_r) {
      if (l == ls[b_l]) {
        total_query(b_l, &res);
      } else {
        for (int i = l; i < rs[b_l]; ++i) {
          partial_query(i, &res);
        }
      }
      for (int i = b_l + 1; i < b_r; ++i) {
        total_query(i, &res);
      }
      if (r == rs[b_r]) {
        total_query(b_r, &res);
      } else {
        for (int i = ls[b_r]; i < r; ++i) {
          partial_query(i, &res);
        }
      }
    } else {
      for (int i = l; i < r; ++i) {
        partial_query(i, &res);
      }
    }
    return res;
  }
};

}  // namespace emthrm

Back to top page