Stern-Brocot树是什么，能解释下吗？
摘要：P1797 【模板】Stern-Brocot 树 洛谷同步题解。 前置知识：(a perp b) 等价于存在 (x, y) 使得 (ax + by = 1)。 Stern-Brocot 树是一个包含着所有
P1797 【模板】Stern-Brocot 树
洛谷同步题解。
前置知识：\(a \perp b\) 等价于存在 \(x, y\) 使得 \(ax + by = 1\)。
Stern-Brocot 树是一个包含着所有 \(m \perp n\) 的全部非负的分数 \(\frac{m}{n}\) 的二叉树结构；其思想是从 \(0\) 阶 Stern-Brocot 序列 \(\{\frac{0}{1}, \frac{1}{0} \}\) 出发，高阶 Stern-Brocot 序列由以下递归操作定义：
对于一个 \(k\) 阶 Stern-Brocot 序列，在其任意两个相邻分数 \(\frac{m}{n}\) 与 \(\frac{m'}{n'}\) 之间插入它们的中位分数 \(\frac{m + m'}{n + n'}\) 后形成的序列即为 \(k + 1\) 阶 Stern-Brocot 序列。
例如：
\(1\) 阶是 \(\{ \frac{0}{1}, \frac{1}{1}, \frac{1}{0} \}\)。
\(2\) 阶是 \(\{ \frac{0}{1}, \frac{1}{2}, \frac{1}{1}, \frac{2}{1}, \frac{1}{0} \}\)。
\(3\) 阶是 \(\{ \frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{1}, \frac{3}{2}, \frac{2}{1}, \frac{3}{1}, \frac{1}{0} \}\)。
容易看作二叉树的结构：
每个分数都是 \(\frac{m + m'}{n + n'}\) 的形式，其中 \(\frac{m}{n}\) 是左上方离它最近的祖先，\(\frac{m'}{n'}\) 是右上方离它最近的祖先。
oi-wiki 上的图较为形象，大家可以看着理解下：
为什么树上的都是最简分数？为什么不会重复出现某个分数？为什么所有可能的非负的最简分数都会在树上出现？
容易发现这样一个性质，如果 \(\frac{m}{n}\) 和 \(\frac{m'}{n'}\) 在某一阶的 Stern-Brocot 序列中相邻，那么必然满足：
\[m'n - mn' = 1
\]
证明考虑数学归纳法，初始 \(0\) 阶时有 \(1 \cdot 1 - 0 \cdot 0 = 1\)；若当前 \(k\) 阶 Stern-Brocot 序列中满足条件，那么在 \(\frac{m}{n}\) 与 \(\frac{m'}{n'}\) 中间插入的 \(\frac{m + m'}{n + n'}\)，相当于要证明：
\[(m' + m)n - m(n + n') = 1
\]
\[m'(n + n') - (m + m') n' = 1
\]
第一个直接拆开 \(m'n + mn - mn - mn' = m'n - mn' = 1\)，第二个同理；于是得证。
同时，上面 \(m'n - mn' = 1\) 这个式子也可以说明 \(m \perp n, m' \perp n'\)，那么可以得到树上的所有分数必然是最简分数。
然后来考虑插入的分数的大小关系，显然有：
\[\frac{m}{n} < \frac{m + m'}{n + n'} < \frac{m'}{n}
\]
即一个中位分数在它原先两个值的中间，于是树上必然没有重复的分数。
好，接下来要证所有正的最简分数 \(\frac{a}{b}\) 都在树上出现，考虑反证法，初始显然：
\[\frac{m = 0}{n = 1} < \frac{a}{b} < \frac{m' = 1}{n' = 0}
\]
然后假设当前阶段有：
\[\frac{m}{n} < \frac{a}{b} < \frac{m'}{n'}
\]
考虑 \(\frac{m + m'}{n + n'}\) 与 \(\frac{a}{b}\) 的大小关系：
若 \(\frac{m + m'}{n + n'} = \frac{a}{b}\)，与命题矛盾，退出。
若 \(\frac{m + m'}{n + n'} < \frac{a}{b}\)，令 \(m \gets m + m', n' + n\)。
否则 \(\frac{m + m'}{n + n'} > \frac{a}{b}\)，令 \(m' \gets m + m', n' \gets n + n'\)。
考虑证明这个过程不会无限进行下去，因为：
\[\begin{cases} \frac{a}{b} - \frac{m}{n} > 0 \\ \frac{m'}{n'} - \frac{a}{b} > 0 \end{cases}
\]
即：
\[\begin{cases} an - mb > 0 \\ m'b - n'a > 0 \end{cases}
\]
显然 \(an - mb, m'b - n'a\) 都是整数，于是：
\[\begin{cases} an - mb \ge 1 \\ m'b - n'a \ge 1 \end{cases}
\]
然后必然有：
\[(m' + n')(an - mb) + (m + n)(m'b - n'a) \ge m' + n' + m + n
\]
前面把 \(a\) 和 \(b\) 专门提出来：
\[a(n(m' + n') - n'(m + n)) + b(m'(m + n) - m(m' + n'))
\]
然后它们的系数可以根据 \(m'n - mn' = 1\) 化简成 \(1\)，于是：
\[a + b \ge m' + n' + m + n
\]
而上面每次操作中 \(m' + n' + m + n\) 都会增加，于是至多进行 \(a + b\) 次后就会退出，即找到 \(\frac{a}{b}\)；于是证明了所有非负分数即正有理数都在树上，可以将 Stern-Brocot 树看作一个有理数的数系。
因为每个正最简分数只出现一次，所以其与树上从根到它的路径是一一对应的，即我们可以用字母 \(L, R\) 来表示当前节点是往左右哪个儿子去走，一串 \(L, R\) 组成的序列就唯一的表示了一个位置；例如 \(LRRL\) 表示 \(\frac{1}{1} \to \frac{1}{2} \to \frac{2}{3} \to \frac{3}{4} \to \frac{5}{7}\)；特别的，对于 \(\frac{1}{1}\) 用 \(I\) 来表示。
考虑这样一个问题，给出一组 \(L, R\) 组成的字符串 \(S\)，求出其对应的分数是什么？
容易想到从初始 \(\frac{1}{1}\) 开始，动态维护这个点是由左右哪两个节点合并的，初始是 \(\frac{m = 0}{n = 1}, \frac{m' = 1}{n' = 0}\)：
若 \(L\) 往左走：那么左祖先不会变，右祖先会变成当前节点；即 \(m' \gets m + m', n' \gets n + n'\)。
若 \(R\) 往右左：同理，那么右祖先不会变，左祖先会变成当前节点；即 \(m \gets m + m', n \gets n + n'\)。
大家理解的时候可以看前面那个树的图来理解；然后我们就可以写下如下代码解决：
inline pair<int, int> getLR(string s){
int len = s.size();
int m = 0, n = 1, m_ = 1, n_ = 0;
for(int i = 0; i < len; ++i){
if(s[i] == 'L')
m_ = m + m_, n_ = n + n_;
else
m = m + m_, n = n + n_;
}
return mkp(m + m_, n + n_);
}
当长度很长时，即给定是 \(L/R\) 每次走几次，也可以根据式子直接做：
inline pair<int, int> getLR(vector<pair<char, int>> s){
int len = s.size();
int m = 0, n = 1, m_ = 1, n_ = 0;
for(int i = 0; i < len; ++i){
if(s[i].fi == 'L')
m_ = s[i].se * m + m_, n_ = s[i].se * n + n_;
else
m = m + s[i].se * m_, n = n + s[i].se * n_;
}
return mkp(m + m_, n + n_);
}
这种还是太程序性了，数学语言怎么表示？容易想到矩阵，即初始：
\[M(S) = \begin{pmatrix} n & n' \\ m & m' \end{pmatrix}
\]
这里为啥不用像分数那样上面分子下面分母呢？主要是此时初始根节点的状态 \(M(I) = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}\) 这是一个单位矩阵，而用分数的表示形式的话不是单位矩阵要多乘一个矩阵，形式上也不那么清晰。
然后考虑：
\[M(SL) = \begin{pmatrix} n & n + n' \\ m & m + m' \end{pmatrix}
\]
\[M(SR) = \begin{pmatrix} n + n' & n' \\ m + m' & m' \end{pmatrix}
\]
那么可以推出 \(L, R\) 矩阵：
\[L = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}
\]
\[R = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}
\]
即：
\[M(SL) = M(S) L, M(SR) = M(S) R
\]
于是求 \(M(S)\) 时，可以看作是 \(S\) 中的 \(L, R\) 作矩阵乘法，例如 \(M(LRRL) = LRRL = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 3 & 4 \\ 2 & 3 \end{pmatrix}\)。
于是求 \(S\) 所对应的分数只需要经过矩阵运算得到：
\[f(S) = f(\begin{pmatrix} n & n' \\ m & m' \end{pmatrix}) = \frac{m + m'}{n + n'}
\]
那么现在考虑给定一个分数 \(\frac{m}{n}\)，求其唯一对应 \(LR\) 序列这个问题？这就比较简单了，根据生成规则，我们知道 Stern-Brocot 树是一颗二叉搜索树，即左子树的点都比它小，右子树的点都比它大，于是可以通过比较与当前位置的值来决定。
那么可以写下如下代码：
inline string backLR(int m, int n){
string ans = "";
Mat S;
while(1){
auto t = f(S);
if(t == mkp(m, n))
break;
if(mkp(m, n) < t){
S = S * L;
ans.push_back('L');
}
else{
S = S * R;
ans.push_back('R');
}
}
return ans;
}
显然，这个效率较为低下，且要进行矩阵运算；考虑怎么优化一下，注意到：
\[RS = \begin{pmatrix} n & n' \\ m + n & m' + n'\end{pmatrix}
\]
\[LS = \begin{pmatrix} n + m& n' + m' \\ m& m'\end{pmatrix}
\]
那么：
\[f(RS) = \frac{n + n'}{m + n + m' + n'} = f(S) + 1
\]
\[f(LS) = \frac{n + m + n' + m'}{m + m'}
\]
\[\frac{1}{f(LS)} = \frac{1}{f(LS)} + 1
\]
设 \(F(\frac{p}{q})\) 表示其对应的字符串；那么我们可以看出，若第一步为 \(R\)，则 \(\frac{m}{n} > 1\)，否则第一步为 \(L\)，则 \(\frac{m}{n} < 1\)，于是可以递归的去做：
\[\frac{m}{n} = f(RS) \to \frac{m - n}{n} = f(S) (m > n)
\]
\[F(\frac{m}{n}) = R + F(\frac{n}{m - n}) (m > n)
\]
\[\frac{m}{n} = f(LS) \to \frac{m}{n - m} = f(S) (m < n)
\]
\[F(\frac{m}{n}) = L + F(\frac{m}{n - m}) (m <n)
\]
那么可以写出如下代码：
inline string backLR(int m, int n){
string ans = "";
while(m != n){
if(m < n){
ans.push_back('L');
n = n - m;
}
else{
ans.push_back('R');
m = m - n;
}
}
return ans;
}
你发现这特别像更像减损法，于是可以用辗转相除法类似的思路去优化，即：
inline vector<pair<char, int>> backLR(int m, int n){
vector<pair<char, int>> ans;
while(m && n && m != n){
if(m < n){
if(n % m == 0)
ans.push_back({'L', n / m - 1});
else
ans.push_back({'L', n / m});
n = n % m;
}
else{
if(m % n == 0)
ans.push_back({'R', m / n - 1});
else
ans.push_back({'R', m / n});
m = m % n;
}
}
return ans;
}
此时就可以做到 \(O(\log n)\) 复杂度去找对应的路径。
然后对于一个分数 \(\frac{p}{q}\)，考虑其在树上一个子树 \(S\)，显然 \(S\) 是无限大的，但是显然其有界，在 \((\frac{a}{b}, \frac{c}{d})\) 之间，那么怎么求出 \(a, b, c, d\) 呢？回到前面每次插入的中位分数在两个值之间的性质，于是这只是换一个问法，显然只是在问合并出 \(\frac{p = a + c}{q = b + d}\) 的是哪两个分数，比较简单，求出 \(\frac{p}{q}\) 的 \(LR\) 串后模拟一下即可。
对于树上问题，容易想到 LCA，那么考虑 Stern-Brocot 树上的两个点 \(\frac{a}{b}, \frac{c}{d}\)，怎么求出它们的 LCA？容易发现，找到 \(\frac{a}{b}, \frac{c}{d}\) 的 \(LR\) 串 \(F(\frac{a}{c}), F(\frac{c}{d})\)，它们 LCP 的长度就是它们 LCA 的深度；而这个长度是容易求的，然后它们的 LCA 就是这个 LCP 对应的节点，套用上面函数一下即可。
同理，\(\frac{p}{q}\) 的树上 \(k\) 级祖先也是可以算出 \(F(\frac{p}{q})\) 后删掉末尾的 \(k\) 个字符后套用前面函数得出。
显然单次时间复杂度都是 \(O(\log w)\)，总时间复杂度为 \(O(T \log w)\)。
link
完整代码：
#include<bits/stdc++.h>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define lowbit(x) x & (-x)
#define fi first
#define se second
#define popcnt(x) __builtin_popcount(x)
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
#define mkp(x, y) make_pair(x, y)
using namespace std;
typedef __int128 __;
typedef long double lb;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
inline ll read(){
ll x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9'){
if(c == '-')
f = -1;
c = getchar();
}
while(c >= '0' && c <= '9'){
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return x * f;
}
inline void write(ll x){
if(x < 0){
putchar('-');
x = -x;
}
if(x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
inline pair<int, int> getLR(vector<pair<char, int>> s){
int len = s.size();
int m = 0, n = 1, m_ = 1, n_ = 0;
for(int i = 0; i < len; ++i){
if(s[i].fi == 'L')
m_ = s[i].se * m + m_, n_ = s[i].se * n + n_;
else
m = m + s[i].se * m_, n = n + s[i].se * n_;
}
return mkp(m + m_, n + n_);
}
inline vector<pair<char, int>> backLR(int m, int n){
vector<pair<char, int>> ans;
while(m && n && m != n){
if(m < n){
if(n % m == 0)
ans.push_back({'L', n / m - 1});
else
ans.push_back({'L', n / m});
n = n % m;
}
else{
if(m % n == 0)
ans.push_back({'R', m / n - 1});
else
ans.push_back({'R', m / n});
m = m % n;
}
}
return ans;
}
inline pair<int, int> getkfa(int m, int n, int k){
auto V = backLR(m, n);
int sum = 0, len = V.size();
for(int i = 0; i < len; ++i)
sum += V[i].se;
if(sum < k)
return mkp(-1, -1);
vector<pair<char, int>> fa;
for(int i = 0; i < len; ++i){
if(!k)
break;
if(V[i].se <= k){
fa.push_back(V[i]);
k -= V[i].se;
}
else{
fa.push_back(mkp(V[i].fi, k));
k = 0;
}
}
return getLR(fa);
}
inline pair<pair<int, int>, pair<int, int>> range(int p, int q){
auto s = backLR(p, q);
int len = s.size();
int m = 0, n = 1, m_ = 1, n_ = 0;
for(int i = 0; i < len; ++i){
if(s[i].fi == 'L')
m_ = s[i].se * m + m_, n_ = s[i].se * n + n_;
else
m = m + s[i].se * m_, n = n + s[i].se * n_;
}
return mkp(mkp(m, n), mkp(m_, n_));
}
inline pair<int, int> getlca(int a, int b, int c, int d){
auto A = backLR(a, b), B = backLR(c, d);
int s1 = 0, s2 = 0;
for(auto v : A)
s1 += v.se;
for(auto v : B)
s2 += v.se;
if(s1 < s2){
swap(a, c), swap(b, d);
swap(A, B);
}
vector<pair<char, int>> lca;
int j = 0;
for(int i = 0; i < (int)A.size(); ++i){
int s = A[i].se;
while(j < (int)B.size() && s){
if(B[j].fi != A[i].fi)
break;
if(B[j].se <= s){
s -= B[j].se;
++j;
}
else{
B[j].se -= s;
s = 0;
}
}
if(j == (int)B.size() || s){
lca.push_back(mkp(A[i].fi, A[i].se - s));
break;
}
lca.push_back(A[i]);
}
return getLR(lca);
}
int T, a, b, c, d, p, q, len, x, k;
char C;
char op[20];
int main(){
T = read();
while(T--){
scanf("%s", op);
if(op[0] == 'E'){
p = read(), q = read();
auto V = backLR(p, q);
write(V.size());
putchar(' ');
for(auto t : V){
putchar(t.fi);
putchar(' ');
write(t.se);
putchar(' ');
}
putchar('\n');
}
else if(op[0] == 'D'){
vector<pair<char, int>> V;
len = read();
while(len--){
C = getchar();
x = read();
V.push_back({C, x});
}
auto t = getLR(V);
write(t.fi);
putchar(' ');
write(t.se);
putchar('\n');
}
else if(op[0] == 'L'){
a = read(), b = read(), c = read(), d = read();
auto t = getlca(a, b, c, d);
write(t.fi);
putchar(' ');
write(t.se);
putchar('\n');
}
else if(op[0] == 'A'){
k = read(), a = read(), b = read();
auto t = getkfa(a, b, k);
if(t.fi < 0){
puts("-1");
continue;
}
write(t.fi);
putchar(' ');
write(t.se);
putchar('\n');
}
else{
a = read(), b = read();
auto t = range(a, b);
write(t.fi.fi);
putchar(' ');
write(t.fi.se);
putchar(' ');
write(t.se.fi);
putchar(' ');
write(t.se.se);
putchar('\n');
}
}
return 0;
}
UVA11350 Stern-Brocot Tree
洛谷同步题解。
模版这有，使用 getLR 即可。
link
P5179 Fraction
洛谷同步题解。
怎么题解区的 Stern-Brocot 树怎么都在递归去做，来一篇 Stern-Brocot 树的依靠树性质的单 \(\log\) 做法。
思路：
首先看看 Stern-Brocot 树的图：
显然这是一颗二叉搜索树，考虑 \(\frac{a}{b}, \frac{c}{d}\) 在树上的关系，分讨一下：
令 \(\frac{x}{y} = \operatorname{LCA}(\frac{a}{b}, \frac{c}{d})\)。
若 \(\frac{x}{y} \ne \frac{a}{b}\) 且 \(\frac{x}{y} \ne \frac{c}{d}\)：即 \(\frac{a}{b}\) 与 \(\frac{c}{d}\) 分别在 \(\frac{x}{y}\) 的左右儿子的子树中，说明必然 \(\frac{a}{b} < \frac{x}{y} < \frac{c}{d}\)，考虑证明 \(\frac{x}{y}\) 就是最优答案；显然的，\(\frac{x}{y}\) 子树内的分数 \(\frac{x'}{y'}\) 必然满足 \(x' \ge x, y' \ge y\)（因为都是以 \(\frac{x}{y}\) 为基础合并出来的），于是子树内满足条件的没有 \(\frac{x}{y}\) 优；而子树外的显然不可能在 \((\frac{a}{b}, \frac{c}{d})\) 之间。
否则 \(\frac{a}{b}\) 与 \(\frac{c}{d}\) 在一条链上，这里只说 \(\frac{c}{d}\) 是其 \(\operatorname{LCA}\) 的情况，另一种对称类似即可：显然 \(\frac{a}{b}\) 在 \(\frac{c}{d}\) 的左儿子 \(lson\) 子树中，那么直接选左儿子作为 \(\frac{p}{q}\) 行吗？不行，因为若 \(\frac{a}{b}\) 在 \(lson\) 的右子树内，那么就不满足条件了，所以再分讨一下：
若 \(\frac{a}{b}\) 在 \(lson\) 的左子树内：那么 \(lson\) 是最优的，证明类似。
否则 \(\frac{a}{b} = lson\) 或者在 \(lson\) 的右子树内怎么办？容易想到，考虑 \(\frac{a}{b}\) 的位置，从 \(lson\) 出发后一直往右跳，直到 \(\frac{a}{b}\) 在当前点左子树中或者等于当前点：
若 \(\frac{a}{b}\) 等于当前点：那么最优的是 \(\frac{a}{b}\) 的右儿子。
否则 \(\frac{a}{b}\) 在当前点的左子树中：那么最优的就是当前点。
大家可以自己手摸感受一下。
于是直接在应用 Stern-Brocot 树模版，找到 \(\operatorname{LCA}\) 与找对应路径等；时间复杂度为 \(O(T \log w)\)。
link
AT_abc408_g [ABC408G] A/B < p/q < C/D
洛谷同步题解。
与上面那题一样。