P1797 【模板】Stern-Brocot 树

Rigel · 2025-12-17 12:47:40 · 题解

Stern-Brocot 树是一种维护既约分数的树状结构。

0x00 Stern-Brocot 树的构造

0x01 逐层构造

Stern-Brocot 树可以在构造第 k 阶 Stern-Brocot 序列时得到。

第 0 阶 Stern-Brocot 序列：\dfrac{0}{1},\dfrac{1}{0}，分别代表 0,+\infin。

在第 k 阶 Stern-Brocot 序列每两个相邻的分数 \dfrac{a}{b},\dfrac{c}{d} 之间加入分数 \dfrac{a+c}{b+d}，即可得到第 (k+1) 阶 Stern-Brocot 序列。

前几次迭代的结果如下。

将每次迭代新生成的分数连成树状结构，就得到了 Stern-Brocot 树。

图片来自 OI Wiki。

0x02 三元组构造

以三元组 \left(\dfrac{0}{1},\dfrac{1}{1},\dfrac{1}{0}\right) 为根结点。

在每个结点 \left(\dfrac{a}{b},\dfrac{p}{q},\dfrac{c}{d}\right) 后分别添加 \left(\dfrac{a}{b},\dfrac{a+p}{b+q},\dfrac{p}{q}\right),\left(\dfrac{p}{q},\dfrac{p+c}{q+d},\dfrac{c}{d}\right) 作为左右子结点，即可构造出 Stern-Brocot 树。

三元组构造与逐层构造等价。

0x03 矩阵表示

Stern-Brocot 树上的每个结点都对应一个矩阵 S=\begin{bmatrix}b&d\\a&c\end{bmatrix}。

其中，根节点对应单位矩阵 I=\begin{bmatrix}1&0\\0&1\end{bmatrix}。

向左子结点移动和向右子结点移动分别对应将当前矩阵右乘以矩阵：

每个矩阵对应的分数即为 f(S)=\dfrac{a+c}{b+d}。

0x10 Stern-Brocot 树的性质

0x11 单调性

Stern-Brocot 树上每一层的分数都是单调递增的。

:::info[证明]{open}

利用数学归纳法。

若 \dfrac{a}{b}<\dfrac{c}{d}，则有 \dfrac{a}{b}<\dfrac{a+c}{b+d}<\dfrac{c}{d}。

归纳起点是 \dfrac{0}{1}<\dfrac{1}{0}，单调性显然成立。

:::

0x12 最简性

Stern-Brocot 树上的分数均为既约分数。

:::info[证明]{open}

我们需要证明每一层相邻的分数 \dfrac{a}{b},\dfrac{c}{d} 都满足：

同样利用数学归纳法。

根结点处是单位矩阵 I，显然成立。

向下移动时，乘以的矩阵 L,R 的行列式均为 1。根据行列式的性质，在下一层同样有：

对于归纳起点 I=\begin{bmatrix}1&0\\0&1\end{bmatrix}，显然成立。

根据裴蜀定理，可知每个分数的分子与分母必然互素。

:::

0x13 完全性

Stern-Brocot 树包含了所有正的最简分数。

:::info[证明]{open}

首先 Stern-Brocot 树是二叉搜索树。

若一个正的最简分数 \dfrac{p}{q} 不在 Stern-Brocot 树上，则搜索 \dfrac{p}{q} 的过程无限长。因此我们需要证明任何正的最简分数 \dfrac{p}{q} 均可在有限步骤内被搜索到。

假设现在已经知道 \dfrac{a}{b}<\dfrac{p}{q}<\dfrac{c}{d}，那么必然有：

两式分别乘以 (c+d) 与 (a+b)：

两式相加，得：

而 bc-ad=1，于是：

每次搜索更深入一层的时候，a+b+c+d 至少增加 1，而 p+q 保持不变，因此搜索必然在有限步内完成。

:::

0x20 本题思路

0x21 ENCODE_PATH

给定分数 \dfrac{p}{q}，求从 Stern-Brocot 树根走到 \dfrac{p}{q} 的路径。

设现在要查找的分数 \dfrac{p}{q} 落在 \dfrac{a}{b} 与 \dfrac{c}{d} 之间，即左边界为 \dfrac{a}{b}，右边界为 \dfrac{c}{d}。

连续 k 次向右子结点移动时，右边界保持不动，左边界移至 \dfrac{a+kc}{b+kd}。

连续 k 次向左子结点移动时，左边界保持不动，右边界移至 \dfrac{ka+c}{kb+d}。

因此，可以直接通过 \dfrac{a+kc}{b+kd}<\dfrac{p}{q} 或 \dfrac{p}{q}<\dfrac{ka+c}{kb+d} 确定向右子节点或左子结点连续移动的次数 k。

初始时左边界为 \dfrac{0}{1}，右边界为 \dfrac{1}{0}。

vp ENC(int x,int y){
    vp ret;
    ret.clear();
    int a=0,b=1,c=1,d=0;
    bool f=1;
    while(!(x==a+c&&y==b+d)){
        if(f){
            int k=(b*x-a*y-1)/(c*y-d*x);
            if(!k){f^=1;continue;}
            ret.pb(mkp('R',k));
            a+=k*c;
            b+=k*d;
        }else{
            int k=(c*y-d*x-1)/(b*x-a*y);
            if(!k){f^=1;continue;}
            ret.pb(mkp('L',k));
            c+=k*a;
            d+=k*b;
        }
        f^=1;
    }
    return ret;
}

0x22 DECODE_PATH

给定从 Stern-Brocot 树根出发的路径，求终点结点上的分数 \dfrac{p}{q}。

模拟即可。

pii DEC(vp tmp){
    int a=0,b=1,c=1,d=0;
    int n=tmp.size();
    for(int i=0;i^n;i++){
        char ch=tmp[i].fi;
        int k=tmp[i].se;
        if(ch=='R'){
            a+=k*c;
            b+=k*d;
        }else{
            c+=k*a;
            d+=k*b;
        }
    }
    return mkp(a+c,b+d);
}

0x23 LCA

给定 \dfrac{a}{b},\dfrac{c}{d}，求 \dfrac{a}{b},\dfrac{c}{d} 的 LCA 上的分数 \dfrac{p}{q}。

分别将 \dfrac{a}{b},\dfrac{c}{d} 进行 ENCODE_PATH 求出路径，再将两条路径的最长公共前缀进行 DECODE_PATH 即可求出 \dfrac{p}{q}。

if(s=="LCA"){
    int a=read(),b=read(),c=read(),d=read();
    vp tmp1=ENC(a,b),tmp2=ENC(c,d),tt;
    tt.clear();
    int n=min(tmp1.size(),tmp2.size());
    for(int i=0;i^n;i++){
        if(tmp1[i]==tmp2[i])tt.pb(tmp1[i]);
        else{
            if(tmp1[i].fi==tmp2[i].fi){
                int k=min(tmp1[i].se,tmp2[i].se);
                tt.pb(mkp(tmp1[i].fi,k));
            }
            break;
        }
    }
    pii ans=DEC(tt);
    printf("%lld %lld\n",ans.fi,ans.se);
}

0x24 ANCESTOR

给定 \dfrac{a}{b},k，求 \dfrac{a}{b} 到根的链上深度为 k 的结点所对应的分数 \dfrac{p}{q}。若不存在，输出 -1。

先将 \dfrac{a}{b} 进行 ENCODE_PATH 求出路径，再将路径的前 k 次移动进行 DECODE_PATH 即可求出 \dfrac{p}{q}。

if(s=="ANCESTOR"){
    int dep=read(),a=read(),b=read();
    vp tmp=ENC(a,b),tt;
    tt.clear();
    int cnt=0;
    int n=tmp.size();
    for(int i=0;i^n;i++){
        cnt+=tmp[i].se;
        if(cnt<=dep)tt.pb(tmp[i]);
        else{
            int k=dep-(cnt-tmp[i].se);
            if(k)tt.pb(mkp(tmp[i].fi,k));
            break;
        }
    }
    if(cnt<dep){
        printf("-1\n");
        return;
    }
    pii ans=DEC(tt);
    printf("%lld %lld\n",ans.fi,ans.se);
}

0x25 RANGE

给定 \dfrac{p}{q}，记在 Stern-Brocot 树中，\dfrac{p}{q} 的子树中的所有分数构成的集合为 S，求 \inf S=\dfrac{a}{b} 和 \sup S=\dfrac{c}{d}。

特别地，对于 0，输出 0 1；对于 +\infin，输出 1 0。