浅谈Stern-brocot树和连分数

· · 算法·理论

Stern-brocot 树是一个二叉搜索树，每个节点的键值是一个有理数，以最简分数的形式记为 \frac{m_i}{n_i}。同时有一个上界分数 \frac{a_i}{b_i} 和一个下界分数 \frac{c_i}{d_i}，表示这个点为根的子树所有键值都在 (\frac{c_i}{d_i},\frac{a_i}{b_i}) 区间内，且满足 m_i=a_i+c_i,n_i=b_i+d_i。也就是说，每个节点的上界下界分数已经蕴含了键值。

这是一棵形态固定的树。生成方式如下：

根节点的下界分数为 \frac{0}{1}，上界分数为 \frac{1}{0}。

节点i，其左儿子的下界分数是 \frac{c_i}{d_i}，上界分数是 \frac{m_i}{n_i}。

其右儿子下界分数是 \frac{m_i}{n_i}，上界分数是 \frac{a_i}{b_i}。

如此生成一颗无限大的二叉树。称一个节点的键值和其上下界分数为相邻分数。

接下来介绍一些性质。

  1. 任意两个相邻分数 \frac{m_1}{n_1}<\frac{m_2}{n_2}，有 m_2n_1-m_1n_2=1。

用归纳法即可直接证明。

  1. 用这种方式直接加出来得到的键值都是最简分数。

由性质1，可知 gcd(m_1,n_1)=gcd(m_2,n_2)=1，即键值是最简分数。

  1. 任意两个点键值不同

由构造方式，可知每个点键值严格介于上下界之间，那么每往下构造一层节点相当于往序列里的每个间隔插入一个数，不会相等。

  1. 任意正有理数都会出现在这棵树上。

设某个有理数 \frac{p}{q}，若其处在某两个相邻分数之间，即 \frac{m_1}{n_1}<\frac{p}{q}<\frac{m_2}{n_2}。

两个不等式拆开可得 qm_1<pn_1，qm_2>pn_2，由于都是整数，可写为 pn_1-qm_1\geq 1，qm_2-pn_2\geq 1。

把 p 消元得到 q(m_2n_1-m_1n_2)\geq n_1+n_2，由性质1化为 q\geq n_1+n_2。

当 n_1+n_2>q 时这个有理数不可能严格介于这两个相邻分数之间。也就是说，不停在树上往下二分，保持有理数在上下界之间，当某个节点的上下界分数的分母之和超过 q 时，这个有理数一定会在树上出现。

由前几个可看出，stern-brocot 树上的节点集合和正有理数可以构成双射。

  1. 对于键值来说是二叉搜索树，对于分子或分母来说是小顶堆。

  2. 有理数 \frac{p}{q} 在树上的深度，级别是 O(\max(p,q))。

  3. 有理数 \frac{p}{q} 在树上到根节点的路径转折点个数级别是 O(\log \max(p,q))。

考虑一个转折点的情况，转折点的儿子将会是转折点和转折点的父节点作为上下界。由于性质5，分子分母相比于转折点的父亲都至少翻倍。则转折点个数只有 \log 个。

接下来，怎么表示这棵树？一般来讲不会全部保存，需要用到的范围很大。但可以高效计算一些相关节点。

当前节点上界为 \frac{a}{b} ，下界为 \frac{c}{d}。

  1. 当前分数值为 \frac{a+c}{b+d}。
  2. 父节点是 b 和 d 当中更小的那一个分数
  3. 向左走 k 步的后代是 \frac{kc+a}{kd+b}，向右走 k 步的后代是 \frac{ka+c}{kb+d}。

通过这些快速计算就可以计算一个无理数在固定精度下的有理逼近。比如某个 \sqrt{a}，在 sbt 上往下二分，往左二分的步数，然后再二分往右走的步数，这样就可以找到分母不超过某个数以内的最佳有理逼近。时间复杂度 O(\log ^2M)。

当然还有一些在具体题目里的应用我就不说了。接下来来介绍连分数。

某个有理数 r，可被表示为如下形式，即连分数表示。

从定义可看出 a_0\geq 0,\forall 1\leq i<n,a_i>0,a_n>1。根据定义可知序列中每个数其实就是这个有理数 r=\frac{p}{q} 里的 p 和 q 做辗转相除的时候的每一步的商。由算法可知，有理数的连分数序列长度级别为 O(\log (\max(p,q)))。

这其实也是一个不断逼近的过程，称这个序列前 k 个位置的连分数表示出来的有理数为 r_k=\frac{p_k}{q_k}，称为渐进分数。

可以看出，每连续2个 r_k 都是一个 r 的上下界，且不断缩小范围。偶数下标的 r_k 都小于 r，且递增，奇数下标的 r_k 都大于 r 且递减。这和 stern-brocot 树的逼近过程有类似之处。

既然这是一个逼近，那么对于无理数来说，也可以类似定义连分数，但是是一个无穷长的序列，是一个极限为此无理数的柯西列。

渐进分数满足如下等式。

p_k=a_kp_{k-1}+p_{k-2},q_k=a_kq_{k-1}+q_{k-2}

证明：我们令 \{p_k\} 和 \{q_k\} 序列按以上方式递推生成， k=0,1 时由 r_0,r_1 生成，我们证明 \frac{p_k}{q_k}=r_k。

用归纳法证明。当 k=0,1 时由定义显然成立。

假设当 n<k 时，任意序列都满足以上等式，当 n=k 时：

r_k=[a_0,a_1,...,a_k]=[a_0,a_1,...,a_{k-1}+\frac{1}{a_k}]=\frac{(a_{k-1}+\frac{1}{a_k})p_{k-2}+p_{k-3}}{(a_{k-1}+\frac{1}{a_k})q_{k-2}+q_{k-3}}=\frac{p_{k-1}+\frac{p_{k-2}}{a_k}}{q_{k-1}+\frac{q_{k-2}}{a_k}}=\frac{p_k}{q_k}

归纳假设成立。

特殊定义 r_{-1}=\frac{1}{0},r_{-2}=\frac{0}{1} ，可将合法递推关系扩展至k=0的情况。

观察渐进分数的递推式，发现和 stern-brocot 树上往某侧走 a_k 步表达式类似。有了这个递推式之后，可将有理数在 stern-brocot 树的位置用连分数进行对应。

由上面两个图可以发现初始在根节点，向右走 a_0 步，再向左走 a_1 步，依次往下走，最后一步走 a_n-1 步，就是这个数的位置。这样，连分数序列长度和 stern-brocot 树上转折点个数相同（或者差 1 ），前面说过他们都是 \log 级别。

由图中可知， r_k 这个渐进分数是 r_{k-1} 的左（右）儿子的右（左）后代，所以他们是相邻分数。那么就有 p_kq_{k-1}-p_{k-1}q_k=(-1)^{k-1}。对于一对数 a,b， \frac{a}{b} 化简结果是 \frac{p_n}{q_n}，由 p_nq_{n-1}-p_{n-1}q_n=(-1)^{n-1} ， aq_{n-1}-bp_{n-1}=gcd(a,b)(-1)^{n-1}。也就是说， q_{n-1},p_{n-1} 可作为 ax+by=gcd(a,b) 不定方程的结果。这是扩欧的另一个角度。

由于 r\in[\frac{p_{k-1}}{q_{k-1}},\frac{p_k}{q_k}] （区间可能反过来），有 |r-\frac{p_k}{q_k}|<|\frac{p_{k-1}}{q_{k-1}}-\frac{p_k}{q_k}|=\frac{1}{q_kq_{k-1}}，对 \forall r\in \mathbb{R} 都成立。这可以说明无理数的有理逼近的一个精度。

应用什么的不是特别了解，oi 里可能会有一些比较牵强的题，但是代数或者数论里面好像会有不少比较深刻的应用。其实我去年 12 月份就打算更这个，数算课 pre 我讲的，写了个简略的 ppt，但是因为期末忘了。今年 6 月份学 shor 算法（order finding 部分）的时候突然又用到了这个才想起来。

NOI2024 的 d2t1 不知道能不能用这个做，希望如果有人看到了这里可以教教我。