stern_brocot_tree
クラス · Stern-Brocot 木
struct stern_brocot_tree;
概要
Stern-Brocot 木
正の有理数を既約分数 p/q として木のノードと同一視する。根は 1/1。 各ノードを子孫が成す開区間の左端 lo・右端 hi で保持し、メディアントが そのノードの値になる。左の子へ進む移動を ‘L’、右の子へ進む移動を ‘R’ とし、 パスは連長圧縮 (各要素は (移動文字, 連続回数)) で表す。
計算量
- 単純な親子操作は $O(1)$、分数とパスの変換はEuclid法の反復回数に比例
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
(1) 根1/1を構築する (2) 子孫区間(lo, hi)からノードを構築する |
$O(1)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
value |
このノードが表す既約分数を返す | $O(1)$ |
range |
子孫が成す開区間の左右端を返す | $O(1)$ |
is_root |
根1/1か返す | $O(1)$ |
left |
左の子へk回降りた子孫を返す | $O(1)$ |
right |
右の子へk回降りた子孫を返す | $O(1)$ |
depth |
根からの深さを返す | $O(\log\max(p,q))$ 回のEuclid反復 |
path_from_root |
根からこのノードまでの連長圧縮パスを返す | $O(\log\max(p,q))$ 回のEuclid反復 |
静的メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
from_fraction |
分数fが表すノードを構築する | $O(\log\max(p,q))$ 回のEuclid反復 |
from_path |
連長圧縮パスを根から辿ったノードを構築する | パスの要素数を $L$ として $O(L)$ |
encode |
1/1からfまでの連長圧縮パスを返す | $O(\log\max(p,q))$ 回のEuclid反復 |
decode |
パスが指す既約分数を返す | パスの要素数を $L$ として $O(L)$ |
lca |
2分数の最近共通祖先を返す | 2分数の連長圧縮パス長を $L_1,L_2$ として $O(L_1+L_2)$ |
ancestor |
fの祖先のうち深さkのものを返す | fの連長圧縮パス長を $L$ として $O(L)$ |
nearest |
targetに最も近い、分母がmax_denominator以下の既約分数を返す | $O(\log\max(p, q, \mathrm{max\_denominator}))$ |
search |
単調述語predが真となる最大の分数を分母上限内で返す | 述語呼出し $O(\log^2 \mathrm{max\_denominator})$ 回 |
メンバ型
| 名前 | 説明 | 計算量 |
|---|---|---|
fraction |
ノードを表す分数型 | 型エイリアスで実行時計算量はない |
path |
根からの連長圧縮パス型 | 型エイリアスで実行時計算量はない |
メンバの詳細
(constructor)
// (1)
constexpr stern_brocot_tree();
// (2)
constexpr stern_brocot_tree(fraction lo, fraction hi);
(1) 根1/1を構築する
- 計算量: $O(1)$
(2) 子孫区間(lo, hi)からノードを構築する
- 計算量: $O(1)$
depth
std::int64_t depth() const;
根からの深さを返す
パスを構築せず連長を直接足し上げる。根は0。
- 計算量: $O(\log\max(p,q))$ 回のEuclid反復
from_fraction
static stern_brocot_tree from_fraction(fraction f);
分数fが表すノードを構築する
パスの往復を避け、降下を直接lo/hiへ反映する。
- 計算量: $O(\log\max(p,q))$ 回のEuclid反復
ancestor
static fraction ancestor(std::int64_t k, fraction f);
fの祖先のうち深さkのものを返す
- 戻り値: 存在しなければ無効値{0, 0}
- 計算量: fの連長圧縮パス長を $L$ として $O(L)$
nearest
static fraction nearest(fraction target, std::int64_t max_denominator);
targetに最も近い、分母がmax_denominator以下の既約分数を返す
距離が等しいときは小さい方を返す。target=1/0は非対応。
- 計算量: $O(\log\max(p, q, \mathrm{max\_denominator}))$
search
template <class F>
static fraction search(F pred, std::int64_t max_denominator);
単調述語predが真となる最大の分数を分母上限内で返す
pred(p,q)は分数が小さいほど真で、pred(0,1)は真とする。
- 計算量: 述語呼出し $O(\log^2 \mathrm{max\_denominator})$ 回
関連項目
sbt_fraction— 既約分数 (Stern-Brocot 木のノード)