Bước 1

Khi sử dụng kỹ thuật này, ta cần trả lời rõ ràng 3 câu hỏi sau:
1. t[i] là gì?
2. get(i) là gì?
3. update(i,v) làm gì?

Phải xác định t[i] là gì trước!
Sau đó đến thủ tục update nó khi nào và ntn!
Sau đó khi làm đúng 2 bước trên thì chắc chắn thủ tục get sẽ đúng!

Ta có thể nói thể này:
t[i] là số lượng các số nhỏ hơn i
t[i] + 1: khi gặp 1 số k nào đó < i thì phải cập nhật lại t[i]
Do k < i, nên k phải cập nhật cả t[i+1] => Cập nhật theo chiều GoUp();
(Dùng cách này để biết chiều cập nhật là GoDown hay là GoUp)

Bước 2

Dựng lại cây và chạy demo xem có chạy đúng ý của mình không?

Những chú ý

Những chú ý mà hay bị nhầm!

+) t[i]: Không thể hiện tổng từ 1 đến i, mà t[i] = tổng các node con của nó!
Sử dụng thao tác getBIT(i): để lấy tổng từ a[1] đến a[i] từ các t[j] cần thiết!

+) Phải nắm chắc thứ tự chuyện lên và duyệt xuống của nó, biết chính xác nó đi qua những node nào!

Một số ghi nhớ nhanh

+) Khi chạy lên nó luôn chạy lên phía cha của mình!
+) Nhưng khi chạy xuống, thì nó chỉ chạy một số nút con ngay dưới nó thôi!
(chứ không phải chạy thẳng 1 mạch về gốc 1)
VD: GoDown(4) : Nó chỉ chạy tới 4 thôi
GoDown(6) : 6->4
GoDown(7) : 7 6 4
GoDown(8) : 8

+) Truy vấn đến cha của nó: i += i & -i;
+) Truy vấn đến con của nó: (không phải con của nó mà tổng sau) i -= i & -i;

*) Thông thường nếu update xuôi thì sẽ get ngược và ngược lại!

Bài tập

1. Bài điển hình sử dụng BIT: NKINV
2. Sử dụng BIT kết hợp quy hoạch động: KINV

Advertisements