Bài 13.1: Thuật toán Bubble Sort và cải tiến

Chào mừng quay trở lại với hành trình khám phá thế giới của Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ cùng nhau tìm hiểu về một trong những thuật toán sắp xếp kinh điển và đơn giản nhất từng được giảng dạy: Bubble Sort, hay còn gọi là Sắp xếp nổi bọt. Mặc dù có thể không phải là lựa chọn hiệu quả nhất cho các tập dữ liệu lớn, việc hiểu cách Bubble Sort hoạt động là một nền tảng quan trọng để tiếp cận các thuật toán sắp xếp phức tạp hơn sau này. Hơn nữa, chúng ta sẽ khám phá cách cải tiến nó để hoạt động tốt hơn trong một số trường hợp đặc biệt.

Bubble Sort Hoạt Động Thế Nào?

Ý tưởng cốt lõi của Bubble Sort cực kỳ đơn giản: nó lặp đi lặp lại việc so sánh hai phần tử liền kề và hoán đổi chúng nếu chúng không đúng thứ tự. Quá trình này được thực hiện qua nhiều "lượt" (pass) trên toàn bộ mảng. Trong mỗi lượt, phần tử lớn nhất còn lại sẽ "nổi bọt" (bubble up) đến vị trí cuối cùng đúng của nó.

Hãy hình dung mảng như một cột nước và các số là những "bọt khí" có kích thước khác nhau (số lớn hơn thì "nổi" nhanh hơn). Trong mỗi lần đi qua, bọt lớn hơn sẽ vượt qua bọt nhỏ hơn ngay bên cạnh, đẩy nó lên trên.

Xem xét một ví dụ đơn giản với mảng [5, 1, 4, 2, 8]. Chúng ta muốn sắp xếp nó theo thứ tự tăng dần.

Lượt 1:

So sánh 5 và 1: 5 > 1, hoán đổi. Mảng trở thành [1, 5, 4, 2, 8].
So sánh 5 và 4: 5 > 4, hoán đổi. Mảng trở thành [1, 4, 5, 2, 8].
So sánh 5 và 2: 5 > 2, hoán đổi. Mảng trở thành [1, 4, 2, 5, 8].
So sánh 5 và 8: 5 < 8, không hoán đổi. Mảng vẫn là [1, 4, 2, 5, 8]. Kết thúc Lượt 1, phần tử lớn nhất (8) đã "nổi" đến vị trí cuối cùng đúng của nó.

Lượt 2:

So sánh 1 và 4: 1 < 4, không hoán đổi. Mảng vẫn là [1, 4, 2, 5, 8].
So sánh 4 và 2: 4 > 2, hoán đổi. Mảng trở thành [1, 2, 4, 5, 8].
So sánh 4 và 5: 4 < 5, không hoán đổi. Mảng vẫn là [1, 2, 4, 5, 8]. Lưu ý: Chúng ta không cần so sánh đến phần tử cuối cùng (8) vì nó đã được sắp xếp ở Lượt 1. Kết thúc Lượt 2, phần tử lớn nhất còn lại (5) đã ở đúng vị trí.

Lượt 3:

So sánh 1 và 2: 1 < 2, không hoán đổi. Mảng vẫn là [1, 2, 4, 5, 8].
So sánh 2 và 4: 2 < 4, không hoán đổi. Mảng vẫn là [1, 2, 4, 5, 8]. Kết thúc Lượt 3, phần tử lớn nhất còn lại (4) đã ở đúng vị trí.

Lượt 4:

So sánh 1 và 2: 1 < 2, không hoán đổi. Mảng vẫn là [1, 2, 4, 5, 8]. Mảng đã được sắp xếp hoàn toàn! Đối với một mảng có n phần tử, trong trường hợp xấu nhất, chúng ta sẽ cần n-1 lượt để đảm bảo mảng được sắp xếp.

Code C++ cho Bubble Sort Cơ Bản

Dưới đây là cách cài đặt Bubble Sort cơ bản bằng C++.

#include <iostream>
#include <vector>
#include <algorithm> // Dùng cho std::swap

// Hàm in mảng
void printArray(const std::vector<int>& arr) {
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}

// Hàm sắp xếp Bubble Sort cơ bản
void bubbleSort(std::vector<int>& arr) {
    int n = arr.size();
    // Vòng lặp ngoài: kiểm soát số lượt (pass)
    // Chúng ta cần tối đa n-1 lượt
    for (int i = 0; i < n - 1; ++i) {
        // Vòng lặp trong: thực hiện so sánh và hoán đổi các cặp liền kề
        // Ở mỗi lượt i, n-i phần tử cuối cùng đã được sắp xếp
        // nên chúng ta chỉ cần lặp đến n-1-i
        for (int j = 0; j < n - 1 - i; ++j) {
            // So sánh phần tử hiện tại và phần tử kế tiếp
            if (arr[j] > arr[j+1]) {
                // Nếu không đúng thứ tự, hoán đổi chúng
                std::swap(arr[j], arr[j+1]);
            }
        }
        // (Tùy chọn) In trạng thái mảng sau mỗi lượt để dễ hình dung
        // std::cout << "Sau luot " << i+1 << ": ";
        // printArray(arr);
    }
}

int main() {
    std::vector<int> data = {64, 34, 25, 12, 22, 11, 90};
    int n = data.size();

    std::cout << "Mang truoc khi sap xep: ";
    printArray(data);

    bubbleSort(data);

    std::cout << "Mang sau khi sap xep (Bubble Sort co ban): ";
    printArray(data);

    return 0;
}

Giải thích Code:

#include <iostream> và <vector>: Thư viện cần thiết cho nhập/xuất và sử dụng std::vector.
#include <algorithm>: Chứa hàm tiện ích std::swap để hoán đổi giá trị.
printArray: Hàm phụ trợ để in nội dung của vector.
bubbleSort(std::vector<int>& arr): Hàm chính thực hiện sắp xếp. Nó nhận một tham chiếu đến vector để có thể thay đổi trực tiếp nội dung của vector gốc.
int n = arr.size();: Lấy kích thước của vector.
Vòng lặp ngoài (for (int i = 0; i < n - 1; ++i)): Vòng lặp này chạy n-1 lần, tương ứng với số lượt tối đa cần thiết. Biến i theo dõi số phần tử đã được đưa về cuối mảng và sắp xếp đúng vị trí.
Vòng lặp trong (for (int j = 0; j < n - 1 - i; ++j)): Vòng lặp này thực hiện các so sánh và hoán đổi trong một lượt.
- Nó duyệt từ phần tử đầu tiên (j=0) đến phần tử thứ n-2-i.
- Tại sao lại là n-1-i? Bởi vì ở cuối mỗi lượt i, phần tử lớn nhất chưa được sắp xếp sẽ nằm ở vị trí n-1-i. Các phần tử từ n-1-i đến n-1 đã ở đúng vị trí của chúng sau các lượt trước, nên chúng ta không cần so sánh đến đó nữa.
- So sánh cặp arr[j] và arr[j+1].
if (arr[j] > arr[j+1]): Kiểm tra xem cặp liền kề có sai thứ tự không.
std::swap(arr[j], arr[j+1]);: Nếu sai thứ tự, hoán đổi vị trí của chúng.

Phân Tích Độ Phức Tạp của Bubble Sort Cơ Bản

Phân tích độ phức tạp giúp chúng ta hiểu hiệu suất của thuật toán khi kích thước dữ liệu tăng lên.

Độ phức tạp Thời gian:
- Trong trường hợp xấu nhất (mảng sắp xếp ngược) và trung bình, mỗi lượt (pass) của vòng lặp ngoài sẽ thực hiện khoảng n phép so sánh và có thể là n phép hoán đổi (vòng lặp trong chạy khoảng n lần). Vì vòng lặp ngoài chạy n-1 lần, tổng số phép so sánh và hoán đổi xấp xỉ (n-1) * n. Khi n rất lớn, số này gần bằng n^2. Do đó, độ phức tạp thời gian là O(n^2).
- Trong trường hợp tốt nhất (mảng đã được sắp xếp), Bubble Sort cơ bản vẫn sẽ thực hiện tất cả các phép so sánh. Vòng lặp ngoài chạy n-1 lần, và vòng lặp trong ở lượt đầu chạy n-1 lần, lượt thứ hai chạy n-2 lần, ..., lượt cuối chạy 1 lần. Tổng số phép so sánh vẫn là (n-1) + (n-2) + ... + 1 = n(n-1)/2, xấp xỉ O(n^2). Do đó, độ phức tạp thời gian trong trường hợp tốt nhất của bản cơ bản vẫn là O(n^2).
Độ phức tạp Không gian:
- Bubble Sort là một thuật toán tại chỗ (in-place), nghĩa là nó chỉ cần một lượng không gian bộ nhớ ổn định bổ sung cho các biến tạm thời (như biến dùng để hoán đổi) mà không phụ thuộc vào kích thước của mảng. Độ phức tạp không gian là O(1).

Với độ phức tạp thời gian O(n^2), Bubble Sort trở nên rất chậm khi xử lý các tập dữ liệu lớn (ví dụ: với n = 10000, n^2 = 100,000,000 phép tính!). Đây là lý do tại sao nó ít được sử dụng trong thực tế cho các tác vụ sắp xếp lớn.

Cải Tiến Bubble Sort: Dừng Sớm

Điểm yếu lớn của Bubble Sort cơ bản là nó luôn thực hiện đầy đủ n-1 lượt, ngay cả khi mảng đã được sắp xếp xong từ các lượt trước đó. Chúng ta có thể cải tiến điều này bằng cách thêm một cờ (flag) để theo dõi xem có bất kỳ hoán đổi nào xảy ra trong một lượt hay không.

Nếu trong một lượt duyệt toàn bộ mảng mà không có bất kỳ cặp nào cần hoán đổi, điều đó có nghĩa là mảng đã được sắp xếp hoàn toàn. Khi đó, chúng ta có thể dừng thuật toán ngay lập tức mà không cần thực hiện các lượt tiếp theo.

Hãy xem cách cài đặt cải tiến này:

#include <iostream>
#include <vector>
#include <algorithm> // Dùng cho std::swap

// Hàm in mảng
void printArray(const std::vector<int>& arr) {
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}

// Hàm sắp xếp Bubble Sort có cải tiến (dừng sớm)
void bubbleSortOptimized(std::vector<int>& arr) {
    int n = arr.size();
    bool swapped; // Cờ để kiểm tra có hoán đổi nào xảy ra trong lượt không

    // Vòng lặp ngoài: kiểm soát số lượt (pass)
    // Lặp cho đến khi không còn hoán đổi nào (mảng đã sắp xếp)
    for (int i = 0; i < n - 1; ++i) {
        swapped = false; // Đặt lại cờ cho mỗi lượt

        // Vòng lặp trong: thực hiện so sánh và hoán đổi
        for (int j = 0; j < n - 1 - i; ++j) {
            if (arr[j] > arr[j+1]) {
                std::swap(arr[j], arr[j+1]);
                swapped = true; // Đặt cờ thành true nếu có hoán đổi
            }
        }

        // Nếu không có bất kỳ hoán đổi nào trong vòng lặp trong,
        // tức là mảng đã được sắp xếp. Thoát khỏi vòng lặp ngoài.
        if (swapped == false) {
            std::cout << "Mang da sap xep sau luot " << i + 1 << ". Dung som!" << std::endl;
            break;
        }
        // (Tùy chọn) In trạng thái mảng sau mỗi lượt để dễ hình dung
        // std::cout << "Sau luot " << i+1 << ": ";
        // printArray(arr);
    }
}

int main() {
    // Trường hợp 1: Mảng ngẫu nhiên
    std::vector<int> data1 = {64, 34, 25, 12, 22, 11, 90};
    std::cout << "--- Truong hop 1 (Mang ngau nhien) ---" << std::endl;
    std::cout << "Mang truoc khi sap xep: ";
    printArray(data1);
    bubbleSortOptimized(data1);
    std::cout << "Mang sau khi sap xep (Bubble Sort cai tien): ";
    printArray(data1);
    std::cout << std::endl;

    // Trường hợp 2: Mảng gần sắp xếp (đã sắp xếp)
    std::vector<int> data2 = {10, 20, 30, 40, 50, 60, 70};
    std::cout << "--- Truong hop 2 (Mang da sap xep) ---" << std::endl;
    std::cout << "Mang truoc khi sap xep: ";
    printArray(data2);
    bubbleSortOptimized(data2); // Cần dừng sớm ngay sau lượt đầu tiên
    std::cout << "Mang sau khi sap xep (Bubble Sort cai tien): ";
    printArray(data2);
    std::cout << std::endl;

    // Trường hợp 3: Mảng gần sắp xếp (chỉ vài phần tử sai vị trí)
    std::vector<int> data3 = {1, 5, 2, 8, 4, 9};
     std::cout << "--- Truong hop 3 (Mang gan sap xep) ---" << std::endl;
    std::cout << "Mang truoc khi sap xep: ";
    printArray(data3);
    bubbleSortOptimized(data3); // Cần dừng sớm sau vài lượt
    std::cout << "Mang sau khi sap xep (Bubble Sort cai tien): ";
    printArray(data3);
    std::cout << std::endl;


    return 0;
}

Giải thích Code Cải tiến:

bool swapped;: Khai báo biến boolean swapped để theo dõi trạng thái hoán đổi trong mỗi lượt.
swapped = false;: Tại đầu mỗi lượt mới (trước khi vào vòng lặp trong), chúng ta đặt lại swapped về false.
swapped = true;: Nếu có một phép hoán đổi xảy ra bên trong vòng lặp trong, chúng ta đặt swapped thành true.
if (swapped == false) { break; }: Sau khi vòng lặp trong kết thúc (một lượt đã hoàn thành), chúng ta kiểm tra giá trị của swapped. Nếu nó vẫn là false, nghĩa là không có bất kỳ cặp nào cần hoán đổi trong lượt này, chứng tỏ mảng đã được sắp xếp. Lệnh break sẽ kết thúc ngay lập tức vòng lặp ngoài, dừng thuật toán sớm.

Phân Tích Độ Phức tạp của Bubble Sort Cải tiến

Độ phức tạp Thời gian:
- Trường hợp xấu nhất và trung bình: Nếu mảng sắp xếp ngược hoặc cần nhiều hoán đổi trong hầu hết các lượt, cờ swapped sẽ luôn là true cho đến gần cuối. Thuật toán sẽ vẫn chạy gần đủ n-1 lượt với mỗi lượt ~O(n) so sánh. Do đó, độ phức tạp vẫn là O(n^2).
- Trường hợp tốt nhất (mảng đã được sắp xếp): Ở lượt đầu tiên (i = 0), vòng lặp trong sẽ duyệt qua tất cả n-1 cặp. Vì mảng đã sắp xếp, sẽ không có hoán đổi nào xảy ra, biến swapped vẫn là false. Sau khi vòng lặp trong kết thúc, điều kiện if (swapped == false) sẽ đúng và thuật toán sẽ break ngay lập tức. Nó chỉ thực hiện một lượt duyệt. Do đó, độ phức tạp thời gian trong trường hợp tốt nhất là O(n).
Độ phức tạp Không gian: Vẫn là thuật toán tại chỗ, chỉ cần thêm một biến boolean (swapped), nên độ phức tạp không gian vẫn là O(1).

Cải tiến này mang lại lợi ích đáng kể trong trường hợp mảng đã được sắp xếp hoặc gần sắp xếp, làm cho Bubble Sort trở thành một lựa chọn khá hiệu quả cho các tình huống đó so với phiên bản cơ bản.

Khi nào nên sử dụng Bubble Sort?

Mặc dù có độ phức tạp O(n^2) trong trường hợp tổng quát, Bubble Sort vẫn có chỗ đứng (dù nhỏ) trong thế giới lập trình:

Mục đích Giáo dục: Nó là một trong những thuật toán dễ hiểu và cài đặt nhất, là điểm khởi đầu tuyệt vời cho người mới học về sắp xếp.
Tập dữ liệu rất nhỏ: Đối với mảng chỉ có vài chục phần tử, sự khác biệt giữa O(n^2) và các thuật toán nhanh hơn (như Merge Sort, Quick Sort với O(n log n)) là không đáng kể. Đôi khi sự đơn giản trong cài đặt lại là ưu tiên.
Mảng gần sắp xếp: Với cải tiến dừng sớm, Bubble Sort hoạt động hiệu quả (O(n)) trên các mảng mà hầu hết các phần tử đã ở đúng vị trí, chỉ có một vài phần tử sai lệch nhỏ.

Bài tập ví dụ:

Phép XOR và Cặp Số Đặc Biệt

Trong một buổi tập huấn, huấn luyện viên đã đưa ra một bài toán thú vị cho FullHouse Dev. Họ được yêu cầu tính toán số cặp chỉ số thỏa mãn một điều kiện đặc biệt liên quan đến phép XOR. Với tinh thần ham học hỏi, FullHouse Dev đã bắt tay vào giải quyết bài toán này.

Bài toán

Cho một mảng gồm \(n\) số nguyên \(a_1, a_2, ..., a_n\). Hãy tính số cặp chỉ số \((i, j)\) thỏa mãn \(i < j\) và \(a_i\) xor \(a_j > a_i\).

INPUT FORMAT:

Dòng đầu tiên chứa số nguyên \(n\) - số lượng phần tử trong mảng.
Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, ..., a_n\) cách nhau bởi dấu cách.

OUTPUT FORMAT:

In ra số cặp chỉ số thỏa mãn yêu cầu.

Ràng buộc:

\(1 \leq n \leq 10^5\)
\(1 \leq a_i \leq 10^6\)

Ví dụ

INPUT

5
1 3 1 4 3

OUTPUT

Giải thích

Có 2 cặp chỉ số thỏa mãn điều kiện:

\((1, 2)\): \(1\) xor \(3 = 2 > 1\)
\((1, 4)\): \(1\) xor \(4 = 5 > 1\) Tuyệt vời! Đây là hướng dẫn giải bài toán "Phép XOR và Cặp Số Đặc Biệt" sử dụng C++ một cách hiệu quả, tập trung vào ý tưởng thay vì code hoàn chỉnh.

1. Nhận xét và Phân tích Bài toán:

Bài toán yêu cầu đếm cặp (i, j) với i < j sao cho a[i] ^ a[j] > a[i].
Ràng buộc n \leq 10^5 và a_i \leq 10^6.
Giải pháp vét cạn (duyệt mọi cặp (i, j) với i < j và kiểm tra điều kiện) có độ phức tạp O(n^2), quá chậm với n=10^5. Cần một giải pháp hiệu quả hơn, thường là O(n log(max_a)) hoặc O(n sqrt(max_a)).
Điều kiện a[i] ^ a[j] > a[i] là mấu chốt. Hãy phân tích nó ở mức bit.

2. Phân tích Điều kiện a[i] ^ a[j] > a[i]:

Xét biểu diễn nhị phân của a[i] và a[j]. Phép XOR ^ cho kết quả 1 nếu các bit tương ứng khác nhau, 0 nếu giống nhau.
X > Y trong hệ nhị phân có nghĩa là bit có trọng số cao nhất mà X và Y khác nhau thì bit đó ở X là 1 còn ở Y là 0.
Áp dụng điều này cho a[i] ^ a[j] > a[i]: Điều này xảy ra khi và chỉ khi bit có trọng số cao nhất (từ bit cao đến bit thấp) mà a[i] ^ a[j] và a[i] khác nhau thì bit đó ở a[i] ^ a[j] là 1 còn ở a[i] là 0.
Hãy xem xét bit khác nhau có trọng số cao nhất (k).
- Nếu bit thứ k của a[i] là 0 và bit thứ k của a[j] là 1: Bit thứ k của a[i] ^ a[j] sẽ là 0 ^ 1 = 1. Đối với các bit m > k, a[i] và a[j] giống nhau (vì k là bit khác nhau cao nhất), nên bit thứ m của a[i] ^ a[j] là bit_m(a[i]) ^ bit_m(a[j]) = bit_m(a[i]) ^ bit_m(a[i]) = 0. Nhưng nếu m > k và bit thứ m của a[i] và a[j] giống nhau, thì bit thứ m của a[i] ^ a[j] cũng giống bit thứ m của a[i]. Tức là, cho mọi m > k, bit_m(a[i] ^ a[j]) = bit_m(a[i]). Tại bit k, bit_k(a[i] ^ a[j]) = 1 và bit_k(a[i]) = 0. Do đó, a[i] ^ a[j] chắc chắn lớn hơn a[i].
- Nếu bit thứ k của a[i] là 1 và bit thứ k của a[j] là 0: Bit thứ k của a[i] ^ a[j] sẽ là 1 ^ 0 = 1. Tương tự, cho mọi m > k, bit_m(a[i] ^ a[j]) = bit_m(a[i]). Tại bit k, bit_k(a[i] ^ a[j]) = 1 và bit_k(a[i]) = 1. Trong trường hợp này, bit k không giúp a[i] ^ a[j] lớn hơn a[i]. Sự so sánh phụ thuộc vào các bit thấp hơn, nhưng theo định nghĩa của k là bit khác nhau cao nhất, các bit thấp hơn không thể làm thay đổi kết quả so sánh dựa trên bit k. Thực tế, nếu bit khác nhau cao nhất là k và a[i] có 1 còn a[j] có 0, thì a[i] đã lớn hơn a[j]. Trong trường hợp này, a[i] ^ a[j] sẽ có 1 ở bit k, giống a[i], nhưng các bit thấp hơn có thể khác. Tuy nhiên, điều kiện a[i] ^ a[j] > a[i] KHÔNG được đảm bảo.
Kết luận về điều kiện: a[i] ^ a[j] > a[i] khi và chỉ khi bit có trọng số cao nhất mà a[i] và a[j] khác nhau là bit mà a[i] có giá trị 0 và a[j] có giá trị 1.

3. Ý tưởng Thuật toán Hiệu quả:

Điều kiện phụ thuộc vào cấu trúc bit của các số. Cấu trúc dữ liệu hiệu quả cho các bài toán liên quan đến bit và tiền tố nhị phân là Binary Trie (Cây Tiền Tố Nhị Phân).
Vì cần đếm cặp (i, j) với i < j, ta có thể duyệt mảng a từ trái sang phải (từ j = 0 đến n-1). Với mỗi phần tử a[j], ta cần đếm số phần tử a[i] đã xuất hiện trước đó (i < j) thỏa mãn điều kiện.
Ta sẽ sử dụng một cây Trie để lưu trữ các số a[0], a[1], ..., a[j-1]. Khi xét đến a[j], ta sẽ truy vấn cây Trie này để đếm các a[i] phù hợp, sau đó thêm a[j] vào cây Trie.

4. Xây dựng Cây Trie và Thuật toán:

Cấu trúc Trie Node: Mỗi node trong cây Trie sẽ có 2 con (trỏ tới node con): child[0] (đại diện cho bit 0) và child[1] (đại diện cho bit 1). Ngoài ra, mỗi node cần lưu trữ số lượng các số đã được chèn mà đi qua node này.
Số bit cần xét: Giá trị lớn nhất của a_i là 10^6. 2^19 < 10^6 < 2^20. Ta cần xét tới 20 bit (từ bit 19 đến bit 0).
Thuật toán Tổng thể:
1. Khởi tạo một cây Trie rỗng với node gốc.
2. Khởi tạo biến đếm tổng số cặp total_pairs = 0.
3. Duyệt qua mảng a từ j = 0 đến n-1. Gọi giá trị hiện tại là val = a[j].
4. Đối với val:
  - Truy vấn Trie: Đếm số lượng a[i] (i < j, tức là các số đã có trong Trie) sao cho a[i] ^ val > a[i]. Quá trình truy vấn đi từ node gốc, từ bit cao nhất (19) đến bit thấp nhất (0).
    - Tại mỗi bit k (từ 19 xuống 0), xét bit thứ k của val (bit_val).
    - Ta đang ở node current_node trong Trie.
    - Chúng ta tìm a[i] trong các nhánh con của current_node.
    - Điều kiện a[i] ^ val > a[i] được thỏa mãn nếu bit khác nhau cao nhất là k, a[i] có 0, val có 1.
    - Xét nhánh con tương ứng với bit (1 - bit_val) (tức là nhánh mà a[i] có bit khác với val tại vị trí k).
      - Nếu bit_val là 1 (tức val có 1 ở bit k, và nhánh con tương ứng với a[i] có 0 ở bit k): Đây là trường hợp có sự khác biệt bit thuận lợi (a[i]=0, val=1). Tất cả các số a[i] nằm trong nhánh con này đều thỏa mãn điều kiện với k là bit khác nhau cao nhất. Cộng số lượng nút trong nhánh con này (current_node->child[0]->count nếu bit_val là 1) vào kết quả truy vấn hiện tại cho val.
      - Nếu bit_val là 0 (tức val có 0 ở bit k, và nhánh con tương ứng với a[i] có 1 ở bit k): Đây không phải là trường hợp thuận lợi (a[i]=1, val=0). Sự khác biệt ở bit k không đảm bảo a[i] ^ val > a[i]. Không cộng gì từ nhánh này dựa trên bit k.
    - Tiếp tục đi xuống nhánh con mà bit giống với bit_val (current_node->child[bit_val]) để kiểm tra các bit thấp hơn. Nếu nhánh này không tồn tại, dừng truy vấn.
  - Cộng kết quả truy vấn này vào total_pairs.
  - Chèn val vào Trie: Đi từ node gốc, theo các bit của val từ cao nhất đến thấp nhất. Nếu một node trên đường đi chưa tồn tại, tạo mới. Tăng biến đếm (count) tại mỗi node trên đường đi.
5. Sau khi duyệt hết mảng, total_pairs là kết quả cuối cùng.

5. Ước lượng Hiệu suất:

Mỗi số a[j] được truy vấn và chèn một lần.
Mỗi thao tác truy vấn hoặc chèn vào Trie mất thời gian O(số bit), tức O(log(max_a)).
Tổng thời gian: O(n log(max_a)). Với n=10^5 và max_a=10^6 (log khoảng 20), đây là khoảng `10^5 20 = 2 * 10^6` phép toán, rất hiệu quả.
Bộ nhớ: Số node trong Trie tối đa là O(n * log(max_a)). Cũng hiệu quả.

Hướng dẫn Code (Conceptual):

Định nghĩa một struct TrieNode chứa TrieNode* children[2] và một biến int count.
Hàm insert(root, val, max_bits): chèn val vào Trie, cập nhật count.
Hàm query(root, val, max_bits): thực hiện logic truy vấn như mô tả ở trên, trả về số lượng a[i] phù hợp.
Trong hàm main: đọc input, khởi tạo root Trie (nullptr cho children, 0 cho count), vòng lặp duyệt mảng, gọi query và insert, cộng dồn kết quả.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.