Binary Index Tree ( cây BIT )

Binary Index Tree ( cây BIT )

Binary Index Tree(gọi tắt là BIT) cũng là một mô hình cây như Interval Tree (IT). Theo ý kiến của mình thì bài nào giải được bằng BIT thì đều giải được bằng IT nhưng chưa chắc giải được bằng IT đã giải được bằng BIT. Cả hai đều lấy dữ liệu được cập nhật dữ liệu từ nút con , đều có thuật toán O(Nlogn) tuy nhiên BIT lại có điểm tốt của nó ở chỗ BIT chỉ cần lưu N nút mà không cần lưu tất cả 2*N nút như ở IT ; còn 1 điểm đặc biệt của BIT nữa, đó là sự ngắn gọn của nó mang lại , ở các bài toán cơ bản hay nâng cao thì code của BIT hầu hết luôn ngắn hơn code IT rất nhiều. Sau đây là mô hình của cây BIT :

       

Mỗi nút X bao gồm bản thân nút X , con của X , con của con X ,…. Cấu trúc của BIT được định nghĩa 1 cách đệ quy như sau :

1. x lẻ: cha[x]=x+1;

2. x chẵn: cha[x]=cha[x div 2]*2;

Thông thường sử dụng BIT chỉ sử dụng 2 lệnh cơ bản sau:

            1.Từ nút X truy xuất đến nút cha[X]

            2.Từ nút X truy xuất đến nút lớn nhất, nhỏ hơn X nhưng không là con của X.

-Để truy xuất tới nút cha[X] ta sử dụng công thức đã được C/m sau: cha[X]= X + X and (X xor (X-1)); hoặc 1 công thức hiệu quả hơn đó là cha[X]=X + X and (-X).

-Để truy xuất tới nút đầu tiên không là con của X( nút X’), ta dùng công thức : X’= X – X and (X xor (X-1));  hoặc X’=X – X and (-X).

   

    Theo như ta thấy các phép toán truy xuất trên chỉ là +,- và các phép toán bit, thực hiện nhanh hơn nhiều so với các phép toán *,/,.. Đây cũng chính là 1 điểm mạnh về tốc độ của BIT so với IT ( ở 1 số bài toán có time chặt, với cùng đpt xấp xỉ O(nlogn) thì code cài bằng BIT vẫn có thể AC trong khi cài bằng IT bị TLE).

    Bây giờ ta sẽ tìm hiểu vai trò của 2 thao tác trên. Đơn giản có thể thấy việc truy xuất tới cha[X] là để cập nhật thông tin được lưu trữ. Và, ngược lại, lệnh thứ 2 chính là dùng để lấy thông tin.

Để dễ hình dung ta xét bài toán co bản sau:

     Cho n số A[1],A[2],…,A[n] (n<=10^5) với m truy vấn (m<=10^5), mỗi truy vấn yêu cầu tính tổng từ A[1]->A[j] (với 1<=j<=n ).

Hướng dẫn :

    Nếu làm cách thông thường dễ thấy trường hợp xấu nhất có đpt là O(n*m) , 1 điều impossible.

Ngoài cách 1 số cách thủ thuật khác thì chúng ta còn có 1 công cụ nữa là sử dụng cây BIT.

Bây giờ chúng ta sẽ tìm hiểu cách áp dụng BIT vào bài này.

Gọi T là mảng chứa cây BIT , lưu thông tin của mảng A.

-        Với thao tác 1. Ta truy xuất đến các nút để cập nhật cho chúng rồi sau đó là cha của chúng .T[x] chứa tổng giá trị của nút X với các nút con cháu của X . Ban đầu khởi tạo mảng T =0. Ta có thủ tục update như sau :

  Procedure   update(i:longint);

                        Var  x:longint;

                        Begin

                                    If (i>n) then exit;

                                    T[i]:=T[i]+A[i];

                                    X:=i+I and (-i);

                                    Update(x);

                        End;

Với thủ tục này ta sẽ cập nhất từng phần tử A[i] cho các nút tổ tiên của i ở cây BIT, vì vậy để có 1 cây hoàn chỉnh ta sẽ for từ 1->n rồi update.

  For i:=1 to n do update(i);

-         Với thao tác thứ 2 ta sẽ tính tổng từ 1->i bằng thủ tục sau :

Sum:=0;

Function   tong(i:longint):longint;

            Var     x:longint;

            Begin

                        If (i<=0) then exit(0);

                        X:=I – I and(-i);

                        Tong:= T[i] + tong(x);

            End;

Tới đây có trong tay 2 thủ tục cơ bản trên chúng ta hoàn toàn có thể cài đặt một cách dễ dàng, dễ dàng hơn rất nhiều nếu chúng ta cài bằng IT.

Từ bài toán trên ta  có 2 bài toán cơ bản khác.

  I.Thay vì trong m truy vấn chỉ có yêu cầu tính tổng thì bây giờ thêm vào đó yêu cầu gán giá trị X cho phần tử thứ I.

Cho m truy vấn với 2 yêu cầu :

1.      Gán giá trị X cho phần tử thứ I (1<=i<=n).

2.      Tính tổng từ A[1]..A[j] (1<=j<=n).

   Với bài toán này chỉ phải thay đổi 1 chút ở phần update.

              Procedure   update(i:longint);

                        Var  xx:longint;

                        Begin

                                    If (i>n) then exit;

                                    T[i]:=T[i]+x-A[i];

                                   

                                    Xx:=i+I and (-i);

                                    Update(xx);

                        End;

Sau đó cập nhật lại giá trị của A[i] mới . A[i]:=x;

II.Thay vì yêu cầu chỉ tính tổng từ 1->j thì yêu cầu tính tổng từ A[i]…A[j]; 

            Ta có A[i]+…+A[j]=(A[1]+A[2]+…+A[j])-(A[1]+A[2]+…+A[i-1])=tong(j)-tong(i-1);