Stern-Brocot Tree
(Src/Number/SternBrocotTree.hpp)

• View this file on GitHub
• Last update: 2025-08-23 22:47:55+09:00
• Include: #include "Src/Number/SternBrocotTree.hpp"

概要

有理数の問題では、この構造を考えると、嬉しいことがあります！

ライブラリの使い方

他のライブラリとは異なり、SternBrocotTreeという名前空間の下で型エイリアスや関数を提供している。

Node

template <sbt_internal::Integer T>
using Node = std::pair<T, T>;

有理数を表す。Tはstd::integralまたは128bit整数である必要がある。

Path

enum Direction {
    Left,
    Right
};

template <sbt_internal::Integer T>
using Path = std::vector<std::pair<Direction, T>>;

Stern-Brocot Tree(SBT)の根からのパスを表す。SBTは二分木であり左子に進むことをLeft、右子に進むことをRightで表す。

パスは非常に長くなることがあるため、連長圧縮して表現されている。

• 既約分数 $\frac{a}{b}$ のパスを連長圧縮するとその長さは $O(\log\max\{a, b\})$ になることが知られている。

Encode

template <sbt_internal::Integer T>
Path<T> Encode(Node<T> node)

node に対応するパスを返す。

計算量: $O(\log \max\{ a, b \})$

Decode

template <sbt_internal::Integer T>
Node<T> Decode(const Path<T>& path)

pathに対応するNodeを返す。

計算量: pathの要素数を $n$ として $O(n)$

LCA

template <sbt_internal::Integer T>
Node<T> LCA(Node<T> p, Node<T> q)

p, qに対応するLCAのNodeを返す。 $p\le \frac{a}{b} \le q$ を満たす $\frac{a}{b}$ であって $b$ が最小であるものを見つけることに対応している。

計算量: Encodeを2回、Decodeを1回呼び出すことがボトルネック

Ancestor

template <sbt_internal::Integer T>
std::optional<Node<T>> Ancestor(u64 dep, Node<T> n)

nに対応するパス上の深さdepの頂点を返す。根の深さを $0$ としている。

計算量: Encode, Decodeをそれぞれ1回呼び出すことがボトルネック

Range

template <sbt_internal::Integer T>
std::pair<Node<T>, Node<T>> Range(Node<T> n)

nの部分木の有理数は有理数の開区間を成す。この両端を返す。

計算量: Decodeを一回呼び出す

Depends on

• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Verified with

• Test/LC/stern_brocot_tree.test.cpp

Code

#pragma once

#include "../Template/TypeAlias.hpp"

#include <algorithm>
#include <concepts>
#include <optional>
#include <utility>
#include <vector>
#include <tuple>

namespace zawa {

namespace SternBrocotTree {

namespace sbt_internal {

template <class T>
concept Integer = std::integral<T> or std::same_as<T, __int128_t> or std::same_as<T, __uint128_t>;

} // namespace sbt_internal

enum Direction {
    Left,
    Right
};

template <sbt_internal::Integer T>
using Path = std::vector<std::pair<Direction, T>>;

template <sbt_internal::Integer T>
using Node = std::pair<T, T>;

template <sbt_internal::Integer T>
Path<T> Encode(Node<T> node) {
    auto [a, b] = node;
    u32 d = [&]() {
        if (a < b) {
            std::swap(a, b);
            return 0;
        }
        else {
            return 1;
        }
    }();
    std::vector<T> quos;
    while (b) {
        quos.push_back(a / b);
        T r = a % b;
        a = b;
        b = r;
    }
    if (quos.size()) {
        quos.back()--;
        if (quos.back() == 0)
            quos.pop_back();
    }
    Path<T> res;
    for (T q : quos) {
        res.push_back({static_cast<Direction>(d), q});
        d ^= 1;
    }
    return res;
}

namespace sbt_internal {

template <Integer T>
std::tuple<Node<T>, Node<T>, Node<T>> Decode(const Path<T>& path) {
    T a = 0, b = 1, c = 1, d = 1, e = 1, f = 0;
    for (auto [direction, step] : path) {
        if (direction == Left) {
            e = c + (step - 1) * a;
            f = d + (step - 1) * b;
            c += step * a;
            d += step * b;
        }
        else if (direction == Right) {
            a = c + (step - 1) * e;
            b = d + (step - 1) * f;
            c += step * e;
            d += step * f;
        } 
    }
    return {Node<T>{a, b}, Node<T>{c, d}, Node<T>{e, f}};
}

} // namespace sbt_internal

template <sbt_internal::Integer T>
Node<T> Decode(const Path<T>& path) {
    return std::get<1>(sbt_internal::Decode(path));
}

template <sbt_internal::Integer T>
Node<T> LCA(Node<T> p, Node<T> q) {
    auto a = Encode(p), b = Encode(q);
    Path<T> path;
    for (usize i = 0 ; i < std::min(a.size(), b.size()) ; i++) {
        if (a[i].first != b[i].first)
            break;
        path.push_back({a[i].first, std::min(a[i].second, b[i].second)});
        if (a[i].second != b[i].second)
            break;
    }
    return Decode(path);
}

// depth is 0-indexed
template <sbt_internal::Integer T>
std::optional<Node<T>> Ancestor(u64 dep, Node<T> n) {
    Path<T> path;
    for (auto [direction, step] : Encode(n)) {
        if (dep == 0)
           break;
        u64 s = std::min<u64>(dep, step);
        path.push_back({direction, s});
        dep -= s;
    }
    if (dep)
        return std::nullopt;
    else
        return Decode(path);
}

template <sbt_internal::Integer T>
std::pair<Node<T>, Node<T>> Range(Node<T> n) {
    Node<T> l, r;
    std::tie(l, std::ignore, r) = sbt_internal::Decode(Encode(n));
    return {l, r};
}

} // namespace SternBrocotTree


} // namespace zawa

#line 2 "Src/Number/SternBrocotTree.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/Number/SternBrocotTree.hpp"

#include <algorithm>
#include <concepts>
#include <optional>
#include <utility>
#include <vector>
#include <tuple>

namespace zawa {

namespace SternBrocotTree {

namespace sbt_internal {

template <class T>
concept Integer = std::integral<T> or std::same_as<T, __int128_t> or std::same_as<T, __uint128_t>;

} // namespace sbt_internal

enum Direction {
    Left,
    Right
};

template <sbt_internal::Integer T>
using Path = std::vector<std::pair<Direction, T>>;

template <sbt_internal::Integer T>
using Node = std::pair<T, T>;

template <sbt_internal::Integer T>
Path<T> Encode(Node<T> node) {
    auto [a, b] = node;
    u32 d = [&]() {
        if (a < b) {
            std::swap(a, b);
            return 0;
        }
        else {
            return 1;
        }
    }();
    std::vector<T> quos;
    while (b) {
        quos.push_back(a / b);
        T r = a % b;
        a = b;
        b = r;
    }
    if (quos.size()) {
        quos.back()--;
        if (quos.back() == 0)
            quos.pop_back();
    }
    Path<T> res;
    for (T q : quos) {
        res.push_back({static_cast<Direction>(d), q});
        d ^= 1;
    }
    return res;
}

namespace sbt_internal {

template <Integer T>
std::tuple<Node<T>, Node<T>, Node<T>> Decode(const Path<T>& path) {
    T a = 0, b = 1, c = 1, d = 1, e = 1, f = 0;
    for (auto [direction, step] : path) {
        if (direction == Left) {
            e = c + (step - 1) * a;
            f = d + (step - 1) * b;
            c += step * a;
            d += step * b;
        }
        else if (direction == Right) {
            a = c + (step - 1) * e;
            b = d + (step - 1) * f;
            c += step * e;
            d += step * f;
        } 
    }
    return {Node<T>{a, b}, Node<T>{c, d}, Node<T>{e, f}};
}

} // namespace sbt_internal

template <sbt_internal::Integer T>
Node<T> Decode(const Path<T>& path) {
    return std::get<1>(sbt_internal::Decode(path));
}

template <sbt_internal::Integer T>
Node<T> LCA(Node<T> p, Node<T> q) {
    auto a = Encode(p), b = Encode(q);
    Path<T> path;
    for (usize i = 0 ; i < std::min(a.size(), b.size()) ; i++) {
        if (a[i].first != b[i].first)
            break;
        path.push_back({a[i].first, std::min(a[i].second, b[i].second)});
        if (a[i].second != b[i].second)
            break;
    }
    return Decode(path);
}

// depth is 0-indexed
template <sbt_internal::Integer T>
std::optional<Node<T>> Ancestor(u64 dep, Node<T> n) {
    Path<T> path;
    for (auto [direction, step] : Encode(n)) {
        if (dep == 0)
           break;
        u64 s = std::min<u64>(dep, step);
        path.push_back({direction, s});
        dep -= s;
    }
    if (dep)
        return std::nullopt;
    else
        return Decode(path);
}

template <sbt_internal::Integer T>
std::pair<Node<T>, Node<T>> Range(Node<T> n) {
    Node<T> l, r;
    std::tie(l, std::ignore, r) = sbt_internal::Decode(Encode(n));
    return {l, r};
}

} // namespace SternBrocotTree


} // namespace zawa

Back to top page