Cấu trúc dữ liệu BIT – Binary Indexed Tree (Fenwick Tree)

Giới thiệu về cây Fenwick (hay còn được gọi là BIT)
BIT-yeulaptrinh.pw

Tổng quát, đặt m = 2k.p (với p là số lẻ). Hay nói cách khác, k là vị trí của bít 1 bên phải nhất của m. Trong Fenwick-Tree, nút có số hiệu m sẽ là nút gốc của một cây con gồm 2k nút có số hiệu từ m- 2k+1 đến m.

Ví dụ:

    – 8 = 23.1, vậy 8 là nút gốc của các nút 1, 2, 3, …, 8.

    – 12 = 22.3, vậy 12 là nút gốc của các nút  9, 10, 11, 12

    – 10 = 21.5, vậy 10 là nút gốc của các nút  9, 10.

    – 7 = 20.7, vậy 7 là nút gốc của chỉ nút  7.

    – 16 = 24.1, vậy 16 là nút gốc của các nút 1, 2, 3, …, 16.

Trong Fenwick-Tree, nút gốc đại diện cho tất cả các nút con của nó. Ý nghĩa của từ đại diện ở đây thường dùng là nút gốc lưu tổng giá trị của các nút con. Vì vậy khi tính toán, ta chỉ cần truy xuất nút gốc là đủ mà không cần thiết phải truy xuất đến các nút con. Xét ví dụ:

       Cho mảng gồm n phần tử a1, a2, …, an. Hãy tính tổng Am =  a1 + a2 + … + am (m ≤ n).

Thay vì sử dụng vòng lặp từ 1 đến m để truy xuất từng phần tử ai một (độ phức tạp O(m)), ta sử dụng cấu trúc FENWICK-TREE như sau:

    – t1 = a1

    – t2 = a1 + a2

    – t3 = a3

    – t4 = a1 + a2 + a3 + a4

    – t5 = a5

    – t6 = a5 + a6

    – t7 = a7

    – t8 = a1 + a2 + a3 + a4+ a5 + a6 + a7 + a8

    – …

    – t12 = a9 + a10 + a11 + a12

    – … (tiếp tục như vậy theo cách xây dựng Fenwick-Tree)

 

    * Để tính A15 (m=15), thay vì phải duyệt từ a1 đến a15, ta chỉ cần tính t8 + t12 + t14 + t15 .

    * Để tính A10, chỉ cần tính t8 + t10

    * Để tính A13, chỉ cần tính t8 + t12 + t13

    * Để tính A16, lấy ngay giá trị t16

Tổng quát với m bất kỳ, biểu diễn m thành dạng nhị phân, sau đó lần lượt xóa các bít 1 của m theo thứ tự từ phải sang trái, tại mỗi bước trung gian chính là chỉ số nút cần truy xuất trong Fenwick-Tree.

Ví dụ: m = 13 có biểu diễn nhị phân là 1101:

     1) 1101 -> truy xuất nút 13

     2) Xóa bít 1 bên phải nhất còn 1100 -> truy xuất nút 12

     3) Xóa bít 1 bên phải nhất còn 1000 -> truy xuất nút 8

     4) Xóa bít 1 bên phải nhất và dừng.

Thao tác truy xuất các nút như trên được gọi là getFENWICK-TREE. May mắn là ta có một công thức rất đơn giản để xóa bít 1 bên phải dùng phép toán AND. Thủ tục getFENWICK-TREE như sau:

int getFENWICK-TREE(int m)
{
            int result = 0;
            for(; m> 0; m &= m-1
            {
                        result += t[m];
            }
            return result;
}

Độ phức tạp của getFENWICK-TREE là O(log2m)

Vấn đề còn lại là làm thế nào để xây dựng được Fenwick-Tree như trên? Cách thực hiện là ban đầu khởi tạo các nút của Fenwick-Tree là 0. Sau đó ứng với mỗi giá trị am thì cập nhật các nút cha liên quan trong cây. Ví dụ:

    – Cập nhật giá trị a5 -> cần cập nhật các nút t5, nút cha t6, nút cha t8, nút cha t16,….

    – Cập nhật giá trị a9 -> cần cập nhật các nút t9, nút cha t10, nút cha t12, nút cha t16,…

    – Cập nhật giá trị a4 -> cần cập nhật các nút t4, nút cha t8, nút cha t16,…

Tổng quát với m bất kỳ, biểu diễn m thành dạng nhị phân, nếu cộng 1 vào bít bên phải nhất của m thì ta được nút cha của m.

Ví dụ, m = 5 có biểu diễn nhị phân là 101:

    1) 101 -> cập nhật nút 5

    2) Cộng 1 vào bít phải nhất thành 0110 -> cập nhật nút 6

    3) Cộng 1 vào bít phải nhất thành 1000 -> cập nhật nút 8

    4) Cộng 1 vào bít phải nhất thành 10000 -> cập nhật nút 16.

Thao tác cập nhật các nút từ con đến cha như trên được gọi là updateFENWICK-TREE. Ta cũng có một công thức rất đơn giản để cộng 1 vào bít 1 bên phải nhất dùng phép toán AND. Thủ tục updateFENWICK-TREE như sau:

void updateFENWICK-TREE(int m, int value)
{
   for(; m<= n; m += m & -m)
   {
        t[m] += value;
   }
}

Độ phức tạp của updateFENWICK-TREE là O(log2n)

Trên đây là lý thuyết về Binary Indexed Tree. Bây giờ ta sẽ áp dụng FENWICK-TREE để giải bài Dãy nghịch thế và Dĩa nhạc 3.

Dãy nghịch thế: (Theo cách vét cạn thì cần xét tất cả các cặp, độ phức tạp là O(n2))

Phác thảo thuật toán:

– Dùng một mảng đếm t[100.000], t[u] cho biết hiện giờ có bao nhiêu số nhỏ hơn u.

– Đầu tiên khởi tạo các phần tử mảng t là 0.

– Duyệt từ cuối mảng lên đầu mảng (i từ n->1), ứng với mỗi ai thực hiện hai thao tác:

    1) Kiểm tra xem hiện giờ có bao nhiêu số nhỏ hơn ai (truy xuất t[ai]).

    2) Cập nhật ai vào mảng t, nghĩa là tăng các phần tử từ t[ai+1] đến t[100.000], mỗi phần tử thêm 1.

Tuy nhiên trong thao tác 2 việc cập nhật như vậy tổng thể độ phức tạp vẫn là O(n2). Bây giờ ta sẽ chuyển mảng t thành cấu trúc FENWICK-TREE. Đối với thao tác 1 dùng getFENWICK-TREE, đối với thao tác 2 dùng updateFENWICK-TREE.

Chương trình hoàn chỉnh

cin>>n;
for(i= 1; i<= n; i++) cin>>a[i];
kq = 0;
for(i= n; i>= 1; i–)
{
            kq += getFENWICK-TREE(a[i]);
            updateFENWICK-TREE(a[i]+1, 1);
}
cout<<kq;

Độ phức tạp là O(nlog2n)

Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Speak Your Mind

*