Tác giả:

• Hà Phước Vũ - Lớp 10A5, Trường THPT chuyên Lê Quý Đôn.

I. Giới thiệu.

Trong thế giới Tin học, Hệ nhị phân (Binary) đóng một vai trò rất quan trọng. Tương tự với trong CP khi Binary cùng với tư tưởng của nó đã tạo ra rất nhiều thuật toán khác nhau và phổ biến như Binary Search, Binary Tree, Binary Lifting,

$...$

Trong bài viết này, chúng ta sẽ tìm hiểu về Hệ tam phân (Ternary) cùng với những thuật toán được tạo ra từ tư tưởng của nó.

II. Các thuật toán liên quan đến Ternary.

Trước khi đọc, các bạn cần phải biết về Hệ tam phân là gì.

1. Ternary Search.

Mặc dù đều là tìm kiếm nhưng khái niệm này với Binary Search là hoàn toàn khác nhau.

1. Sơ lược.

Ternary Search thường được sử dụng để tìm cực trị của một hàm số

$F(x)$ chứa chính xác một cực trị. Khi đó,

$F(x)$ sẽ được chia ra làm

$2$ trường hợp:

• Tăng dần đến cực trị và rồi giảm dần về sau, cực trị này là cực đại.
• Giảm dần đến cực trị và rồi tăng dần về sau, cực trị này là cực tiểu.

2. Cài đặt.

Để ta có thể hình dung về Ternary Search, ta có thể xem qua bài toán sau:

• Cho một hàm số
  $F(x)$ có cực trị nằm trong đoạn
  $[l,r]$. Nhiệm vụ của bạn là tìm ra điểm cực trị đó.

Xét

$2$ vị trí

$m_1$ và

$m_2$ trong đoạn

$[l,r]$ với

$m_1<m_2$. Ta sẽ có

$3$ trường hợp sau:

• Cực trị nằm trong đoạn
  $[l,m_1]$, khi đó thì sẽ có một mối liên hệ lớn bé giữa
  $F(m_1)$ và
  $F(m_2)$ (nghĩa là
  $<$ hoặc
  $>$) (gọi là
  $(1)$).
• Cực trị nằm trong đoạn
  $[m_1,m_2]$, khi đó thì mối liên hệ lớn bé giữa
  $F(m_1)$ và
  $F(m_2)$ sẽ không rõ.
• Cực trị nằm trong đoạn
  $[m_2,r]$, khi đó thì sẽ có một mối liên hệ lớn bé giữa
  $F(m_1)$ và
  $F(m_2)$ (nghĩa là
  $<$ hoặc
  $>$) (gọi là
  $(2)$).

Dễ dàng thấy rằng

$(1)$ và

$(2)$ sẽ hoàn toàn ngược lại nhau. Nếu không xét trường hợp giữa, ta có kết luận như sau:

• Cực trị nằm trong đoạn
  $[l,m_2]$, khi đó thì sẽ có một mối liên hệ lớn bé giữa
  $F(m_1)$ và
  $F(m_2)$ (nghĩa là
  $<$ hoặc
  $>$)
  $(1)$.
• Cực trị nằm trong đoạn
  $[m_1,r]$, khi đó thì sẽ có một mối liên hệ lớn bé giữa
  $F(m_1)$ và
  $F(m_2)$ (nghĩa là
  $<$ hoặc
  $>$)
  $(2)$.

Để chọn

$m_1$ và

$m_2$ một cách tối ưu, ta có thể đặt

$dis=\frac{r-l}{3}$ và đặt

$m_1=l+dis,$

$m_2=r-dis$. Dễ dàng thấy sau mỗi lần chặt, không gian tìm kiểm sẽ giảm đi

$\frac{1}{2}$.

Nếu ta lặp lại việc tìm kiếm trên

$n$ lần thì không gian của đoạn

$[l,r]$ sẽ chỉ bằng

$(\frac{2}{3}{)}^n$ ban đầu. Dựa vào đó, dễ dàng thấy độ lớn của

$n$ tỉ lệ thuận với độ chính xác của thuật toán.

Độ phức tạp của ý tưởng trên là

$O(lo{g}_{2}n)$. Dưới đây là code tham khảo.

double F(double x) {
    // Định nghĩa của hàm F(x).
}
double find(double l, double r) {
    int n = 100; // Có thể thay đổi.
    for (int i = 1; i <= n; i++) {
        double dis = (r-l)/3;
        double m1 = l+dis, m2 = r-dis;
        if (F(m1) ? F(m2)) r = m2; 
        if (F(m1) ? F(m2)) l = m1;
        // 2 dấu ? trên là ngược nhau.
	}
}

2. Ternary Tree.

1. Sơ lược.

Cũng như Binary Tree, mỗi node của Ternary Tree sẽ chứa

$3$ node con. Dưới đây là hình ảnh minh họa một Ternary Tree với

$13$ node.

2. Cài đặt.

Đề dễ hình dung hơn về Ternary Tree, ta có thể xem qua bài toán RMQ và sử dụng Segment Tree để giải. Nếu không nhớ RMQ là gì thì bài toán đấy như sau:

• Cho dãy
  $a$ gồm
  $n$ phần tử, có
  $q$ truy vấn cần trả lời có dạng
  $l$
  $r$. Nhiệm vụ của bạn là với mỗi truy vấn, hãy trả lời
  $\text{min}(a_l,a_{l+1},...,a_r)$.

Để giải bài toán trên, ta chỉ đơn giản là sử dụng thuật toán Segment Tree bằng cách cài đặt Ternary Tree thay Binary Tree như thông thường. Cụ thể hơn, nếu node cha lưu trữ

$\text{min}$ của đoạn

$[l,r]$ thì

$3$ node con của nó sẽ lần lượt lưu trữ

$\text{min}$ của đoạn

$[l,l+\frac{r-l}{3}]$,

$[l+\frac{r-l}{3},$

$r-\frac{r-l}{3}]$,

$[r-\frac{r-l}{3},r]$. Khi đó, số node của cây sẽ không vượt quá

$9\times n$ với độ cao không quá

$lo{g}_{3}n$. Dựa vào đó, ta dễ dàng thấy rằng ta sẽ truy cập một node của cây trong

$O(2\times lo{g}_{3}n)$.

Độ phức tạp của ý tưởng trên là

$O((n+q)\times 2\times lo{g}_{3}n)$. Dưới đây là code tham khảo.

// Hàm update để cập nhật kết quả cho cây.
void update(int nd, int l, int r, int u, int v) {
    int m1 = l+(r-l)/3, m2 = r-(r-l)/3;
    if (u < l || r < u) return;
    else if (l == r) {
        st[nd] = v; return;
    }
    update(nd*3, l, m1, u, v);
    update(nd*3+1, m1+1, m2, u, v);
    update(nd*3+2, m2+1, r, u, v);
    st[nd] = min({st[nd*3], st[nd*3+1], st[nd*3+2]});
}
// Hàm query để lấy kết quả từ cây.
int query(int nd, int l, int r, int u, int v) {
    int m1 = l+(r-l)/3, m2 = r-(r-l)/3;
    if (r < u || v < l) return inf;
    if (u <= l && r <= v) return st[nd];
    int lf = query(nd*3, l, m1, u, v);
    int mi = query(nd*3+1, m1+1, m2, u, v);
    int rt = query(nd*3+2, m2+1, r, u, v);
    return min({lf, mi, rt});
}

Cài đặt Lazy Update và giải các bài toán Range Queries khác sẽ tương tự như trên.

3. Ternary Lifting.

1. Sơ lược.

Tư tưởng cũng sẽ như Binary Lifting, ta sẽ định nghĩa

$lift[i][j]$ là một cái gì đấy thứ

$3^j$ của

$i$. Tuy nhiên, ta cần phải lưu ý một chỗ rằng Ternary có tất cả

$3$ chữ số là

$0,1,2$.

2. Cài đặt.

Đề dễ hình dung hơn về Ternary Lifting, ta có thể xem qua lại bài toán RMQ như trên. Khi cài đặt bằng Binary Lifting, ta còn được biết đến với cái tên là Sparse Table.

Ta sẽ định nghĩa

$dp[i][j]$ là phần tử nhỏ nhất của đoạn

$[i,i+3^j-1]$. Dễ dàng thấy đoạn đó chứa

$3$ đoạn con nhỏ hơn là:

• $[i,i+3^{j-1}-1]$ hay là
  $dp[i][j-1]$.
• $[i+3^{j-1},i+2\times 3^{j-1}-1]$ hay là
  $dp[i+3^{j-1}][j-1]$
• $[i+2\times 3^{j-1}][j-1]$ hay là
  $dp[i+2\times 3^{j-1}][j-1]$.

Từ điều trên, ta có thể tính

$dp[i][j]$ bằng cách lấy

$\text{min}$ của

$3$ cái trên. Và tất nhiên,

$dp[i][0]$

$=$

$a[i]$ với

$a$ mà dữ liệu cung cấp.

Với mỗi truy vấn

$l$

$r$, ta chỉ việc phân tích

$r-l+1$ thành dãy tam phân và xét trường hợp chữ số là

$1$ với

$2$.

Độ phức tạp của ý tưởng trên là

$O((n+q)\times 2\times lo{g}_{3}n)$. Dưới đây là code tham khảo.

int log3(int n) {
    for (int i = 0; i <= 12; i++) {
        if (pw[i] > n) return i-1;
    }
    return 12;
}
void pre() {
    pw[0] = 1; 
    for (int i = 1; i <= 12; i++) pw[i] = pw[i-1]*3;
}
void solve() {
    int n, q; cin >> n >> q; pre();
    for (int i = 1; i <= n; i++) cin >> dp[i][0];
    for (int j = 1; j <= 12; j++) {
        for (int i = 1; i+pw[j]-1 <= n; i++) {
            int lf = dp[i+0*pw[j-1]][j-1];
            int mi = dp[i+1*pw[j-1]][j-1];
            int rt = dp[i+2*pw[j-1]][j-1];
            dp[i][j] = min({lf, mi, rt});
        }
    }
    for (int t = 1; t <= q; t++) {
        int l, r, ans = 1e9; cin >> l >> r;
        for (int i = 12; i >= 0; i--) {
            if (2*pw[i] <= r-l+1) {
                ans = min(ans, dp[l+pw[i]][i]);
                ans = min(ans, dp[l][i]); l += 2*pw[i];
            }
            else if (pw[i] <= r-l+1) {
                ans = min(ans, dp[l][i]); l += pw[i];
            }
        }
        cout << ans << "\n";
    }
}

Cài đặt LCA và các bài toán có thể giải bằng Binary Lifting khác sẽ tương tự như trên.

4. So sánh với Binary.

Qua các thuật toán trên, dễ dàng thấy Ternary sẽ có độ phức tạp chủ yếu là

$O(2\times lo{g}_{3}n)$. Trong khi đó, Binary lại có độ phức tạp chủ yếu là

$O(lo{g}_{2}n)$. Vậy cái nào nhanh hơn?

Ta có một chút biến đổi như sau:

$2\times lo{g}_{3}n=\frac{2\times lo{g}_{10}n}{lo{g}_{10}3}$ và

$lo{g}_{2}n=\frac{lo{g}_{10}n}{lo{g}_{10}2}$.

So sánh

$2\times lo{g}_{3}n$ với

$lo{g}_{2}n$ sẽ tương đương với so sánh

$\frac{2\times lo{g}_{10}n}{lo{g}_{10}3}$ và

$\frac{lo{g}_{10}n}{lo{g}_{10}2}$. Khi lấy tỉ lệ giữa

$2$ phân số này, ta sẽ có

$\frac{2\times lo{g}_{10}2}{lo{g}_{10}3}>1$. Từ đó suy ra

$...$ và

$2\times lo{g}_{3}n\ge lo{g}_{2}n$.

Để rõ hơn, dưới đây là đồ thị của

$2$ hàm số

$y=2\times lo{g}_{3}x$ và

$y=lo{g}_{2}x$.

Qua đó, ta có thể thấy rằng

$lo{g}_{2}n\le 2\times lo{g}_{3}n$ với

$n\ge 1$. Ta cũng suy ra được rằng Binary vẫn sẽ là lựa chọn tối ưu.

III. Tổng kết.

Đây là một bài viết được viết với mục đích giải trí. Tuy nhiên, nó có lẽ sẽ khai sáng đầu óc và bộ não của bạn bởi Ternary thực chất không quá phổ biến trong CP.

Hy vọng bài viết này giúp ích cho bạn một phần nào. Chúc các bạn một ngày vui vẻ.