library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by tko919 Hosted on GitHub Pages — Theme by mattgraham

Stern-Brocot Tree
(Math/sternbrocot.hpp)

• View this file on GitHub
• Last update: 2025-07-13 05:51:38+09:00
• Include: #include "Math/sternbrocot.hpp"

Depends on

• Fraction (Math/fraction.hpp)

Code

#pragma once
#include "Math/fraction.hpp"

namespace SternBrocotTree {
static pair<vector<int>, pair<Frac<ll>, Frac<ll>>> getinfo(Frac<ll> &x);
// R start
static vector<int> encode(Frac<ll> x) {
    return getinfo(x).first;
}
static Frac<ll> decode(vector<int> &v) {
    Frac<ll> L(0, 1), R(1, 0);
    rep(i, 0, v.size()) {
        if (i & 1)
            R = Frac<ll>(L.a * v[i] + R.a, L.b * v[i] + R.b);
        else
            L = Frac<ll>(R.a * v[i] + L.a, R.b * v[i] + L.b);
    }
    return Frac<ll>(L.a + R.a, L.b + R.b);
}
static Frac<ll> lca(Frac<ll> x, Frac<ll> y) {
    auto px = encode(x), py = encode(y);
    vector<int> q;
    rep(i, 0, min(px.size(), py.size())) {
        q.push_back(min(px[i], py[i]));
        if (q.back() != px[i] or q.back() != py[i])
            break;
    }
    return decode(q);
}
static pair<Frac<ll>, Frac<ll>> subtree(Frac<ll> x) {
    return getinfo(x).second;
}
static pair<Frac<ll>, Frac<ll>> child(Frac<ll> x) {
    auto [L, R] = subtree(x);
    Frac<ll> lb(L.a + x.a, L.b + x.b), rb(R.a + x.a, R.b + x.b);
    return {lb, rb};
}
static Frac<ll> la(Frac<ll> x, ll k) {
    auto path = encode(x);
    for (;;) {
        if (path.empty())
            return Frac<ll>(-1, 1);
        if (k <= path.back()) {
            path.back() -= k;
            break;
        } else {
            k = path.back();
            path.pop_back();
        }
    }
    return decode(path);
}
static pair<vector<int>, pair<Frac<ll>, Frac<ll>>> getinfo(Frac<ll> &x) {
    Frac<ll> L(0, 1), R(1, 0), mid(1, 1);
    vector<int> path;
    for (;;) {
        if (mid == x)
            break;
        ll k = ceil<ll>(x.a * L.b - x.b * L.a, x.b * R.a - x.a * R.b) - 1;
        L = Frac<ll>(L.a + k * R.a, L.b + k * R.b);
        mid = Frac<ll>(L.a + R.a, L.b + R.b);
        path.push_back(k);
        if (mid == x)
            break;
        k = ceil<ll>(x.b * R.a - x.a * R.b, x.a * L.b - x.b * L.a) - 1;
        R = Frac<ll>(R.a + k * L.a, R.b + k * L.b);
        mid = Frac<ll>(L.a + R.a, L.b + R.b);
        path.push_back(k);
    }
    return {path, {L, R}};
}
}; // namespace SternBrocotTree

/**
 * @brief Stern-Brocot Tree
 */

#line 2 "Math/fraction.hpp"

template <typename T> struct Frac {
    T a, b;
    Frac(T _a = 0) {
        init(_a, 1);
    }
    Frac(T _a, T _b) {
        init(_a, _b);
    }
    template <typename V> V get() const {
        return V(a) / b;
    }
    Frac &init(T _a, T _b) {
        T g = gcd(_a, _b);
        a = _a / g, b = _b / g;
        if (b < 0)
            a = -a, b = -b;
        return *this;
    }
    Frac inv() const {
        return Frac(b, a);
    }
    Frac operator-() const {
        return Frac(-a, b);
    }
    Frac &operator+=(const Frac &x) {
        return init(a * x.b + x.a * b, b * x.b);
    }
    Frac &operator-=(const Frac &x) {
        return init(a * x.b - x.a * b, b * x.b);
    }
    Frac &operator*=(const Frac &x) {
        return init(a * x.a, b * x.b);
    }
    Frac &operator/=(const Frac &x) {
        return init(a * x.b, b * x.a);
    }
    Frac operator+(const Frac &x) const {
        return Frac(*this) += x;
    }
    Frac operator-(const Frac &x) const {
        return Frac(*this) -= x;
    }
    Frac operator*(const Frac &x) const {
        return Frac(*this) *= x;
    }
    Frac operator/(const Frac &x) const {
        return Frac(*this) /= x;
    }
    bool operator<(const Frac &x) const {
        return a * x.b < b * x.a;
    }
    bool operator>(const Frac &x) const {
        return x < *this;
    }
    bool operator<=(const Frac &x) const {
        return !(x < *this);
    }
    bool operator>=(const Frac &x) const {
        return !(*this < x);
    }
    bool operator==(const Frac &x) const {
        return (*this <= x and x <= *this);
    }
    bool operator!=(const Frac &x) const {
        return !(*this == x);
    }

    friend istream &operator>>(istream &is, Frac &x) {
        return is >> x.a >> x.b;
    }
    friend ostream &operator<<(ostream &os, const Frac &x) {
        return os << x.a << '/' << x.b;
    }
};

/**
 * @brief Fraction
 * @docs docs/fraction.md
 */
#line 3 "Math/sternbrocot.hpp"

namespace SternBrocotTree {
static pair<vector<int>, pair<Frac<ll>, Frac<ll>>> getinfo(Frac<ll> &x);
// R start
static vector<int> encode(Frac<ll> x) {
    return getinfo(x).first;
}
static Frac<ll> decode(vector<int> &v) {
    Frac<ll> L(0, 1), R(1, 0);
    rep(i, 0, v.size()) {
        if (i & 1)
            R = Frac<ll>(L.a * v[i] + R.a, L.b * v[i] + R.b);
        else
            L = Frac<ll>(R.a * v[i] + L.a, R.b * v[i] + L.b);
    }
    return Frac<ll>(L.a + R.a, L.b + R.b);
}
static Frac<ll> lca(Frac<ll> x, Frac<ll> y) {
    auto px = encode(x), py = encode(y);
    vector<int> q;
    rep(i, 0, min(px.size(), py.size())) {
        q.push_back(min(px[i], py[i]));
        if (q.back() != px[i] or q.back() != py[i])
            break;
    }
    return decode(q);
}
static pair<Frac<ll>, Frac<ll>> subtree(Frac<ll> x) {
    return getinfo(x).second;
}
static pair<Frac<ll>, Frac<ll>> child(Frac<ll> x) {
    auto [L, R] = subtree(x);
    Frac<ll> lb(L.a + x.a, L.b + x.b), rb(R.a + x.a, R.b + x.b);
    return {lb, rb};
}
static Frac<ll> la(Frac<ll> x, ll k) {
    auto path = encode(x);
    for (;;) {
        if (path.empty())
            return Frac<ll>(-1, 1);
        if (k <= path.back()) {
            path.back() -= k;
            break;
        } else {
            k = path.back();
            path.pop_back();
        }
    }
    return decode(path);
}
static pair<vector<int>, pair<Frac<ll>, Frac<ll>>> getinfo(Frac<ll> &x) {
    Frac<ll> L(0, 1), R(1, 0), mid(1, 1);
    vector<int> path;
    for (;;) {
        if (mid == x)
            break;
        ll k = ceil<ll>(x.a * L.b - x.b * L.a, x.b * R.a - x.a * R.b) - 1;
        L = Frac<ll>(L.a + k * R.a, L.b + k * R.b);
        mid = Frac<ll>(L.a + R.a, L.b + R.b);
        path.push_back(k);
        if (mid == x)
            break;
        k = ceil<ll>(x.b * R.a - x.a * R.b, x.a * L.b - x.b * L.a) - 1;
        R = Frac<ll>(R.a + k * L.a, R.b + k * L.b);
        mid = Frac<ll>(L.a + R.a, L.b + R.b);
        path.push_back(k);
    }
    return {path, {L, R}};
}
}; // namespace SternBrocotTree

/**
 * @brief Stern-Brocot Tree
 */

Back to top page