Cây Stern-Brocot
Cây nhị phân chứa mọi phân số dương tối giản đúng một lần, dựng bằng phép trung vị. Dùng để tìm kiếm nhị phân trên số hữu tỉ, xấp xỉ phân số với mẫu giới hạn và tìm phân số đơn giản nhất trong một khoảng.
Cây Stern-Brocot (Stern-Brocot tree) là cây nhị phân tìm kiếm vô hạn chứa mọi phân số dương tối giản, mỗi phân số đúng một lần. Nó được dựng chỉ bằng một phép toán: trung vị (mediant) của hai phân số và là . Đường đi từ gốc tới chính là thuật toán Euclid trên , và độ dài đường đi khi nén theo đoạn bằng độ dài liên phân số của , tức .
Cây này là công cụ để tìm kiếm nhị phân trên tập số hữu tỉ: tìm phân số mẫu không quá gần một số thực nhất, phân số "đơn giản nhất" trong một khoảng, phân số thứ trong một dãy phân số có thứ tự, hoặc giải các bài mà một quá trình "cộng tử với tử, mẫu với mẫu" xuất hiện ngầm.
Ý tưởng / Trực giác
Cách dựng. Bắt đầu với hai biên và (vô cực). Nút gốc là trung vị . Mỗi nút có một biên trái và biên phải , giá trị là trung vị ; con trái nhận biên , con phải nhận biên .
0/1 .................................................... 1/0
1/1
1/2 2/1
1/3 2/3 3/2 3/1
1/4 2/5 3/5 3/4 4/3 5/3 5/2 4/1
Bổ đề 1 (định thức bằng 1). Với hai biên kề nhau của mọi nút, . Chứng minh: đúng với : . Thay biên phải bằng trung vị: ; thay biên trái cũng vậy. Hệ quả: mọi nút là tối giản (một ước chung của tử và mẫu sẽ chia hết ), và nó nằm thực sự giữa hai biên.
Bổ đề 2 (mọi phân số đều xuất hiện). Nếu với thì và . Chứng minh: và (là số nguyên dương), nên ; tương tự cho . Vậy khi đi xuống cây theo hướng của , mẫu của nút tăng thực sự mỗi bước nhưng không bao giờ vượt , nên sau hữu hạn bước ta gặp đúng . Bổ đề này cũng nói: trung vị của hai biên là phân số có mẫu nhỏ nhất (và tử nhỏ nhất) nằm giữa hai biên.
Đường đi là thuật toán Euclid. Từ đi ngược lên: nếu thì nút nằm ở nhánh phải và nút cha có dạng ; nếu thì ở nhánh trái với cha . Đó là Euclid dạng trừ. Một loạt bước cùng hướng gộp thành một phép chia, nên đường đi nén có dạng với là liên phân số của (số hạng cuối giảm 1).
Tìm kiếm nhị phân trên số hữu tỉ. Cho một vị từ đơn điệu (đúng với phân số nhỏ, sai với phân số lớn) và giới hạn mẫu . Duy trì hai biên (pred đúng) và (pred sai). Lặp: dịch với lớn nhất còn giữ pred đúng và mẫu ; rồi dịch tương tự. Khi trung vị có mẫu vượt , theo bổ đề 2 không còn phân số mẫu nào nằm giữa, nên là hai phân số kề nhau cần tìm. Nếu đi từng bước một, số bước có thể tới (hoặc vô hạn với ); dùng nhân đôi rồi tìm nhị phân cho , mỗi đoạn tốn lần gọi pred, và số lần đổi hướng là độ dài liên phân số .
Ví dụ chạy tay
Đường đi tới . So với từng nút:
| Bước | Biên trái | Biên phải | Nút (trung vị) | So với | Đi |
|---|---|---|---|---|---|
| 1 | lớn hơn | R | |||
| 2 | nhỏ hơn | L | |||
| 3 | lớn hơn | R | |||
| 4 | bằng | dừng |
Đường đi nén là R1 L1 R1. Cách Euclid cho cùng kết quả: , bước R, còn bước L, còn bước R, còn . Liên phân số , số hạng cuối giảm 1 thành . Tương tự, có đường đi L2 R1 L1.
Tìm hai phân số mẫu kẹp (pred: ):
| Vòng | Thao tác | Thử | Kết quả |
|---|---|---|---|
| 1 | dịch về | ? sai | |
| 1 | dịch về : | sai, đúng | , |
| 2 | dịch về : | , đúng; sai | , |
| 2 | dịch về : | sai, mẫu ; mẫu quá | , |
| 3 | trung vị có mẫu | dừng |
Kết quả , và . Phân số có mẫu nhỏ nhất nằm thực sự giữa và là trung vị .
Cài đặt
sb_search nhận vị từ pred(p, q) tùy ý, nên dùng được cho mọi bài "tìm phân số lớn nhất thỏa điều kiện đơn điệu". Khi pred so sánh với một phân số, nhân chéo bằng __int128 để tránh tràn.
typedef long long ll;
// Đường đi từ gốc 1/1 tới p/q (p, q > 0, nguyên tố cùng nhau), nén theo đoạn: (ký tự, số lần).
// 'R' = sang phải (lớn hơn), 'L' = sang trái. Chính là thuật toán Euclid.
vector<pair<char, ll>> sb_path(ll p, ll q) {
vector<pair<char, ll>> path;
while (p != q) {
if (p > q) {
ll k = (p - 1) / q; // số bước R liên tiếp, dừng trước khi p <= 0
path.push_back({'R', k});
p -= k * q;
} else {
ll k = (q - 1) / p;
path.push_back({'L', k});
q -= k * p;
}
}
return path;
}
// Ngược lại: từ đường đi suy ra phân số. Giữ hai biên trái a/b, phải c/d; nút hiện tại là trung vị.
pair<ll, ll> sb_node(const vector<pair<char, ll>>& path) {
ll a = 0, b = 1, c = 1, d = 0; // biên 0/1 và 1/0
for (auto [ch, k] : path) {
if (ch == 'R') { a += k * c; b += k * d; } // k lần: biên trái = trung vị
else { c += k * a; d += k * b; } // k lần: biên phải = trung vị
}
return {a + c, b + d};
}
// pred(p, q) đơn điệu: đúng với phân số nhỏ, sai với phân số lớn (đúng tại 0/1, sai tại 1/0).
// Trả về L = phân số lớn nhất có pred đúng và R = phân số nhỏ nhất có pred sai,
// xét các phân số mẫu <= N. R có thể là 1/0. Mỗi lần đổi hướng: nhân đôi rồi tìm nhị phân.
pair<pair<ll, ll>, pair<ll, ll>> sb_search(ll N, function<bool(ll, ll)> pred) {
ll a = 0, b = 1, c = 1, d = 0;
while (true) {
bool moved = false;
for (int side = 0; side < 2; side++) {
// side 0: L += s*R, cần mẫu <= N và pred đúng; side 1: R += s*L, cần pred sai
auto ok = [&](ll s) {
ll p = side == 0 ? a + s * c : c + s * a, q = side == 0 ? b + s * d : d + s * b;
return q <= N && pred(p, q) == (side == 0);
};
ll s = 0, step = 1;
while (ok(s + step)) { s += step; step *= 2; } // nhân đôi
for (; step > 0; step /= 2) // rồi thu hẹp
if (ok(s + step)) s += step;
if (s > 0) moved = true;
if (side == 0) { a += s * c; b += s * d; }
else { c += s * a; d += s * b; }
}
if (!moved) break; // trung vị (a+c)/(b+d) có mẫu > N
}
return {{a, b}, {c, d}};
}
// Phân số có mẫu nhỏ nhất nằm thực sự giữa a/b và c/d (0 <= a/b < c/d, b, d > 0).
pair<ll, ll> simplest_between(ll a, ll b, ll c, ll d) {
ll k = a / b; // tách phần nguyên chung
a -= k * b;
c -= k * d;
if (c > d) return {k + 1, 1}; // số nguyên k+1 nằm trong khoảng
if (a == 0) return {k * (d / c + 1) + 1, d / c + 1}; // dạng 1/q với q nhỏ nhất
auto [p, q] = simplest_between(d, c, b, a); // lấy nghịch đảo: (d/c, b/a)
return {k * p + q, p}; // nghịch đảo lại (q/p) rồi cộng k
}
# Đường đi từ gốc 1/1 tới p/q (p, q > 0, nguyên tố cùng nhau), nén theo đoạn: (ký tự, số lần).
# "R" = sang phải (lớn hơn), "L" = sang trái. Chính là thuật toán Euclid.
def sb_path(p, q):
path = []
while p != q:
if p > q:
k = (p - 1) // q # số bước R liên tiếp, dừng trước khi p <= 0
path.append(("R", k))
p -= k * q
else:
k = (q - 1) // p
path.append(("L", k))
q -= k * p
return path
# Ngược lại: từ đường đi suy ra phân số. Giữ hai biên trái a/b, phải c/d; nút hiện tại là trung vị.
def sb_node(path):
a, b, c, d = 0, 1, 1, 0 # biên 0/1 và 1/0
for ch, k in path:
if ch == "R":
a, b = a + k * c, b + k * d # k lần: biên trái = trung vị
else:
c, d = c + k * a, d + k * b # k lần: biên phải = trung vị
return a + c, b + d
# pred(p, q) đơn điệu: đúng với phân số nhỏ, sai với phân số lớn (đúng tại 0/1, sai tại 1/0).
# Trả về L = phân số lớn nhất có pred đúng và R = phân số nhỏ nhất có pred sai,
# xét các phân số mẫu <= N. R có thể là 1/0. Mỗi lần đổi hướng: nhân đôi rồi tìm nhị phân.
def sb_search(N, pred):
a, b, c, d = 0, 1, 1, 0
while True:
moved = False
for side in (0, 1):
# side 0: L += s*R, cần mẫu <= N và pred đúng; side 1: R += s*L, cần pred sai
def ok(s):
if side == 0:
p, q = a + s * c, b + s * d
else:
p, q = c + s * a, d + s * b
return q <= N and pred(p, q) == (side == 0)
s, step = 0, 1
while ok(s + step): # nhân đôi
s += step
step *= 2
while step > 0: # rồi thu hẹp
if ok(s + step):
s += step
step //= 2
if s > 0:
moved = True
if side == 0:
a, b = a + s * c, b + s * d
else:
c, d = c + s * a, d + s * b
if not moved:
break # trung vị (a+c)/(b+d) có mẫu > N
return (a, b), (c, d)
# Phân số có mẫu nhỏ nhất nằm thực sự giữa a/b và c/d (0 <= a/b < c/d, b, d > 0).
def simplest_between(a, b, c, d):
k = a // b # tách phần nguyên chung
a -= k * b
c -= k * d
if c > d:
return k + 1, 1 # số nguyên k+1 nằm trong khoảng
if a == 0:
return k * (d // c + 1) + 1, d // c + 1 # dạng 1/q với q nhỏ nhất
p, q = simplest_between(d, c, b, a) # lấy nghịch đảo: (d/c, b/a)
return k * p + q, p # nghịch đảo lại (q/p) rồi cộng k
Ví dụ gọi: sb_search(4, [&](ll p, ll q) { return (__int128)p * 10 <= (__int128)7 * q; }) trả về như bảng ở trên.
Độ phức tạp
| Thao tác | Thời gian | Bộ nhớ |
|---|---|---|
sb_path(p, q), sb_node |
||
sb_search với giới hạn mẫu |
lần gọi pred |
|
simplest_between |
đệ quy | |
| Đi xuống từng bước một (không nén) | tới |
Số đoạn của đường đi bằng độ dài liên phân số, bị chặn bởi số bước của thuật toán Euclid: (mỗi hai bước, số lớn ít nhất giảm một nửa). Trong sb_search, mỗi đoạn tìm bằng nhân đôi rồi chia đôi, lần gọi pred; nếu pred tự tốn (ví dụ một tổng phần nguyên kiểu Euclid) thì tổng là .
⚠️ Lỗi thường gặp
- Đi xuống từng bước: với hay , đường đi không nén dài tới hoặc bước. Luôn gộp các bước cùng hướng bằng phép chia hoặc nhân đôi.
- Đếm thừa một bước ở đoạn cuối: khi chia hết cho (ví dụ ), số bước R là , không phải ; vì vậy code dùng . Phân số chưa tối giản làm vòng lặp không dừng ở : rút gọn trước.
- Tràn số khi nhân chéo: so sánh bằng với các giá trị cỡ cần
__int128; khi nhân đôi , tử số tạm thời cũng có thể vượtlong longnếupredkhông chặn sớm. - Biên vô cực : khi , dịch không tăng mẫu, nên giới hạn mẫu không chặn được ; vị từ bắt buộc phải sai với các phân số đủ lớn, nếu không vòng nhân đôi chạy mãi.
- Nhầm "mẫu nhỏ nhất" với "gần nhất": trung vị của hai biên kề nhau là phân số mẫu nhỏ nhất trong khoảng, nhưng phân số mẫu gần nhất phải so khoảng cách tới cả và sau khi tìm xong.
Biến thể / Mở rộng
- Cây Calkin-Wilf: cùng tập phân số, con trái của là , con phải là ; duyệt theo tầng cho dãy của dãy Stern. Đường đi tới một phân số vẫn là thuật toán Euclid, chỉ đảo thứ tự các bước so với Stern-Brocot.
- Dãy Farey : các phân số trong có mẫu , theo thứ tự tăng; hai phần tử kề nhau thỏa và phần tử chen vào đầu tiên là trung vị. Phần tử kế tiếp sau là với .
- Phân số thứ / xấp xỉ tốt nhất: kết hợp
sb_searchvới một hàm đếm số phân số (tổng phần nguyên kiểu Euclid ). - Bao lồi các điểm nguyên dưới một đường cong: mỗi cạnh của bao lồi là một hướng tìm bằng cây Stern-Brocot, dùng để đếm điểm nguyên dưới cung tròn hay dưới hyperbol.
- Liên hệ: Thuật toán Euclid mở rộng (cùng cấu trúc thương số), Sắp xếp & Tìm kiếm nhị phân (tìm nhị phân trên số nguyên), Số lớn và __int128.
Bài tập luyện
- Hàm số (icpc22mbe): (Very Hard) Tìm nhỏ nhất với cho một dãy truy hồi; đó là dãy Stern, và là chỉ số của trên cây Calkin-Wilf, đọc ra từ đường đi Euclid (cần số lớn).
- Cam, táo và dãy thẻ (fruitcard): (Expert) Tìm dãy thẻ (in dạng nén) để chia hết cam và táo với ; mỗi lá thẻ là một phép lấy trung vị, nên dãy thẻ là đường đi tới trên cây Stern-Brocot, tồn tại khi và chỉ khi .
- Dãy phân số vô hạn (icpc23nati): (Expert) Tìm phân số thứ trong dãy các với ; tìm kiếm nhị phân trên cây Stern-Brocot với vị từ đếm .
Bình luận