SB树

Milthm · 2026-10-14 07:21:50 · 算法·理论

~~SB 树~~ Stern-Brocot 树是一个二叉搜索树，它包含了全部非负有理数，是存储分数（或二元组）的高效数据结构（？

建树

初始时你有一个三元组 (\frac{0}{1}, \frac{1}{1}, \frac{1}{0})，注意，这个树上每个节点都形如 (\frac{a}{b}, \frac{a+c}{b+d}, \frac{c}{d})。

然后依次往下递归建树，令当前节点为 (\frac{a}{b}, \frac{a+c}{b+d}, \frac{c}{d})，则它的左节点为 (\frac{a}{b}, \frac{2a+c}{2b+d}, \frac{a+c}{b+d})，右节点为 (\frac{a+c}{b+d}, \frac{a+2c}{b+2d}, \frac{c}{d})。

显然没有人喜欢看式子，我们来给出 SB 树的前 4 行：

当然也有可能是你在 oi-wiki 上看到的这个：

这个只是把相邻三元组两边重复的分数合一块了。

性质

单调性

注意到

\frac{a}{b}<\frac{2a+c}{2b+d}<\frac{a+c}{b+d}<\frac{a+2c}{b+2d}<\frac{c}{d},

所以每一层的分数都是单调的。

最简性

首先注意到每个三元组的任意两个相邻分数 \frac{a}{b}, \frac{c}{d}，都满足 bc-ad=1。理由是注意到最初的三元组显然满足，然后观察建树的过程，你会发现左节点 (\frac{a}{b}, \frac{2a+c}{2b+d}, \frac{a+c}{b+d})、右节点 (\frac{a+c}{b+d}, \frac{a+2c}{b+2d}, \frac{c}{d}) 的任意两个相邻分数按照上述规则减一减都等于 bc-ad，于是就可以一直往上跳跳到初始三元组，故全都满足。

那么这个最简性如何证明？考虑反证，假设有一个分数 \frac{p}{q} 不是最简分数。由于它肯定不是边上的 \frac{0}{1} 和 \frac{1}{0}，所以它肯定是由两个分数 \frac{a}{b}<\frac{c}{d} 插入中位得到的，即 p=a+c,\ q=b+d。由于上面证明的 bc-ad=1，则

bp-aq=b(a+c)-a(b+d)=bc-ad=1.

但 \frac{p}{q} 不是最简分数，所以 \gcd(p,q)>1。同时 \gcd(p,q)\mid p 且 \gcd(p,q)\mid q，所以 \gcd(p,q)\mid bp-aq，即 \gcd(p,q)\mid 1，这与 \gcd(p,q)>1 矛盾，于是得证。

完全性

首先众所周知，如果 \frac{a}{b}<\frac{p}{q}<\frac{c}{d}，那么 p\ge a+c,\ q\ge b+d。这是因为 bp-aq\ge 1,\ cq-dp\ge 1。令 n=bp-aq,\ m=cq-dp，则

p=\frac{am+cn}{bc-ad}=am+cn,\qquad q=\frac{bm+dn}{bc-ad}=bm+dn,

于是当且仅当 m=n=1 时可以同时取等。

假设存在一个 \frac{p}{q} 不在 SB 树里。我们可以从根节点开始，\frac{0}{1}<\frac{p}{q}<\frac{1}{0}。如果 \frac{p}{q}=\frac{0+1}{1+0}=\frac{1}{1}，那么 \frac{p}{q} 就在这个树里了；所以它一定不等于任何中位分数，因此可以一路向下进入左或右子节点。而每一步新区间的端点之和都会严格增大，最终会超过 p,q，矛盾。

故不存在不在 SB 树里的分数。

说实话这几个性质除了单调性基本没什么用，看看得了。

基础操作

查找一个分数

观察建树过程，你会发现从一个节点 (\frac{a}{b}, \frac{a+c}{b+d}, \frac{c}{d}) 一路往右跳，跳了 k 步，那么三元组最左的分数就是 \frac{a+kc}{b+kd}；一路往左跳，跳了 k 步，那么三元组最右的分数就是 \frac{ka+c}{kb+d}。

于是从根节点开始，先一路往右跳，跳到头记录最左分数，再往左跳，跳到头记录最右分数，一路往下走。假设是这样的一个数列

\frac{p_0}{q_0}, \frac{p_1}{q_1}, \dots, \frac{p_k}{q_k}.

我们往前面加上初始三元组两端的 \frac{p_{-2}}{q_{-2}}=\frac{0}{1},\ \frac{p_{-1}}{q_{-1}}=\frac{1}{0}，设第 i 次往左或右跳了 a_i 次（从 0 开始），然后你就会发现

\frac{p_i}{q_i}=\frac{a_i p_{i-1}+p_{i-2}}{a_i q_{i-1}+q_{i-2}}.

这个可能不好懂，你考虑 (\frac{a}{b}, \frac{a+c}{b+d}, \frac{c}{d}) 向右跳 k 步后的三元组是

\left(\frac{a+kc}{b+kd}, \frac{a+(k+1)c}{b+(k+1)d}, \frac{c}{d}\right),

此时我们再往左跳 l 步，那么三元组就会变成

\left(\frac{a+kc}{b+kd}, \frac{(l+1)a+(l+1)kc+c}{(l+1)b+(l+1)kd+d}, \frac{l(a+kc)+c}{l(b+kd)+d}\right),

所以最右端的分数就是 \frac{l(a+kc)+c}{l(b+kd)+d}。

向左跳再向右本质上是上述过程翻转，所以也是一样的。

然后注意到这个递推式子刚好和连分数的形式相符，于是

\frac{p_i}{q_i}=[a_0,a_1,\dots,a_i].

可以把连分数列出来观察。

注意到我们求的节点是三元组的中间分数，设其为 \frac{p}{q}。由于最后一次跳跃不管向右还是向左，该三元组没有记录的一边一定是上一次跳跃记录的那个分数，所以

\frac{p}{q}=\frac{p_k+p_{k-1}}{q_k+q_{k-1}}=[a_0,a_1,\dots,a_k,1].

一个分数的连分数是用辗转相除法得到的，所以得到连分数形式就可以得到路径，复杂度 O(\log \min(p, q))。

可以观察代码：

struct frac {
    int a, b;
    frac(int _a = 0, int _b = 0) : a(_a), b(_b) {}
    frac operator + (const frac &oth) const { return {a + oth.a, b + oth.b}; }
    frac operator + (const int &oth) const { return {a + oth * b, b}; }
    frac operator - (const int &oth) const { return {a - b * oth, b}; }
    frac operator * (const int &oth) const { return {a * oth, b * oth}; }
    bool operator != (const frac &oth) const { return a != oth.a || b != oth.b; }
    frac inv() {
        frac ans = {b, a};
        return ans;
    }
};
struct path { 
    char c; 
    int n; 
};
vector<path> fnd(frac x) { 
    int to = x.a > x.b; // 大于 1 就往右，否则往左
    if (!to) x.inv();
    vector<path> ans;
    while (x.b) {
        int k = x.a / x.b;
        ans.pb({(to ? 'R' : 'L'), k});
        x = x - k, x = x.inv(), to ^= 1;
    }
    if (ans.size()) {
        if (ans.back().n == 1) ans.pop_back();
        else ans.back().n--;
    } // 连分数的最后一位是 1，需要处理
    return ans;
}

获得一个分数

根据刚才推的连分数递推即可。

frac get(vector<path> x) {
    frac p = {0, 1}, q = {1, 0};
    for (path i : x) {
        if (i.c == 'L') q = p * i.n + q; 
        else p = p + q * i.n;
    }
    return p + q;
}

最佳有理近似

最佳有理近似的定义：

对于实数 x 和分数 \frac{a}{b}，如果对任意 0<d\le b 且 \frac{c}{d}\neq\frac{a}{b}，都有 |x-\frac{c}{d}|>|x-\frac{a}{b}|，则我们称 \frac{a}{b} 为 x 的最佳有理近似。

而在 SB 树上，每一个结点的所有祖先都是它的最佳有理近似，理由是由于一条路径是一个连分数展开，故选取连分数的一段前缀显然是最接近原分数的。

所以求最佳有理近似就是求这个结点的一个祖先。

frac anc(frac x, int k) { // 第 k 个祖先（第 k 个最佳有理近似）
    vector<path> p = fnd(x), ans;
    int dep = 0;
    for (path a : p) {
        dep += a.n;
        if (dep >= k) { 
            a.n -= dep - k, ans.pb(a); 
            break; 
        }
        ans.pb(a);
    }
    if (dep >= k) return get(ans);
    return {-1, 0}; // 无解
}

子树覆盖范围

从全集 [\frac{0}{1}, \frac{1}{0}] 开始，考虑一个收缩的过程，每次判断在中点（即中位分数 \frac{a+c}{b+d}）的哪边，然后把集合收缩到一边，直到刚好夹住，此时的集合两边就是 inf 和 sup，复杂度 O(\log \max(p, q))。

int cross(frac x, frac y) { return x.b * y.a - x.a * y.b; }
pair<frac, frac> rge(frac x) {
    frac l = {0, 1}, r = {1, 0};
    int to = x.a > x.b; // 大于 1 往右，否则往左
    while (x != l + r) {
        if (to) {
            int t = (cross(l, x) - 1) / cross(x, r); // 算能一直收缩几次，-1 是因为不能取等
            l = l + r * t;
        } 
        else {
            int t = (cross(x, r) - 1) / cross(l, x);
            r = r + l * t;
        }
        to ^= 1;
    }
    return {l, r};
}

范围最优分数

以最小分母为例，设当前区间为 \frac{a}{b} < x < \frac{c}{d}。

若 \lfloor a/b \rfloor + 1 < \frac{c}{d}，则整数 \lfloor a/b \rfloor + 1 在区间内，直接返回它（分母为 1 最小）。

否则，令 k = \lfloor a/b \rfloor，将区间变为 (\frac{a-kb}{b}, \frac{c-kd}{d})。此时左端点 < 1，且由于没有整数在区间内，右端点也 \le 1。

注意，如果 a-kb = 0，区间为 (0, \frac{c-kd}{d})，最小分母的分数为 \frac{1}{\lfloor \frac{d}{c-kd} \rfloor + 1}，再加上 k 得到答案。

否则区间在 (0,1) 内，取倒数后变为 (\frac{d}{c-kd}, \frac{b}{a-kb})，递归求解得到 \frac{p}{q}，原答案即为 k + \frac{q}{p} = \frac{k p + q}{p}。

复杂度 O(\log \max(a,b,c,d))

frac best(frac a, frac b) {
    int k = a.a / a.b;
    if ((k + 1) * b.b < b.a) return {k + 1, 1};
    a = a - k, b = b - k;
    frac ans;
    if (a.a == 0) ans = {b.b / b.a + 1, 1};
    else ans = best(b.inv(), a.inv());
    return ans.inv() + k;
}

SB树

建树

性质

单调性

最简性

完全性