Cấu trúc của Binary Indexed Tree được định nghĩa 1 cách đệ quy như sau:

Binary Tree

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

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

Như vậy cha[i] không phụ thuộc vào số nút của cây mà phụ thuộc trực tiếp vào giá trị I. Lưu ý với 1 cây N nút thì với i=1..N, cha[i]>n coi như cha[i] không tồn tại.

Hình minh hoạ sau sẽ cho thấy rõ hơn cấu trúc của 1 binary indexed tree:

Cũng như trong interval tree, thông tin được lưu ở 1 nút binary indexed tree là thông tin của nó và tất cả các nút con của nó (các phần tử ở các nút này bị nó quản lý). Thông tin ở các nút được tích luỹ dần dần lên trên. Nhưng thay vì số nút rất nhiều như ở cây interval, ta chỉ cần dùng 1 mảng O(N) để lưu trữ toàn bộ thông tin dữ liệu của cây binary indexed tree. Cải thiện về bộ nhớ này giúp ích đáng kể trong môi trường bị hạn chế bộ nhớ, đặc biệt trong Turbo Pascal khi mà bộ nhớ chỉ là 64Kb.

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

1. Từ nút I truy xuất tới nút cha[i].

2. Từ nút I truy xuất tới nút lớn nhất, nhỏ hơn I và không là con của I, gọi là I’.

Nếu căn cứ vào định nghĩa cha[i] ta có thể xác định 2 thông tin này trong O(logN) nhưng có 1 cách hiệu quả hơn nhiều:

- Để truy xuất tới cha[i] ta dựa vào công thức đã được CM sau:

cha[i]= i + i and (i xor (i-1));

Công thức trên là công thức thường được mọi người sử dụng nhưng có những công thức hiệu quả hơn: cha[i]= i + i and (-i) = i + i and (1+not i)

- Để truy xuất tới nút đầu tiên không là con của I ta dùng công thức:

I’= i - i and (i xor (i-1)) = i – i and (-i) = i and (i-1);

Các phép toán được dùng 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à điểm mạnh về tốc độ của binary indexed tree so với interval tree.

Vậy, 2 phép toán này được dùng để làm gì? Đơn giản có thể thấy việc truy xuất tới cha[i] 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ựa vào lệnh này ta có thể dễ dàng lấy được thông tin tổng hợp từ tất cả các nút từ 1 tới N: [thông tin 1..n]=A[n]+[thông tin 1..N’], trong đó A[n] là thông tin lưu trữ tại N, dấu “+” biểu hiện cho sự hợp thông tin, đôi khi có thể là phép nhân. Theo định nghĩa N’ thì công thức trên đúng.

Ví dụ: [thông tin 1..15]=A[15]+A[14]+A[12]+A[8].

Độ phức tạp trong mỗi lần lấy thông tin không vượt quá O(logN+1).

Giới hạn của Binary Indexed Tree chính là vì lệnh thứ 2 chỉ tác dụng lấy thông tin trong nửa khoảng đầu tiên là 1..I mà không cho lấy thông tin tổng hợp đoan I..J bất kì trong O(logN) trong trường hợp tổng quát. Do vậy tác dụng của Binary indexed Tree cũng bị hạn chế hơn so với Interval tree. Binary Indexed Tree chỉ thực sự tuyệt vời trong các trường hợp sau:

- Thông tin được lưu trữ phải có tính tích luỹ, như tổng, tích, giá trị min, max...

- Thông tin sử dụng luôn nằm trong nửa khoảng, hoặc có tính cộng trừ nhân chia được (trong trường hợp này, thông tin có thể lấy trong các đoạn I..J bất kì trong O(logN) vì [thông tin (i..j)] = [thông tin (1..j)] – [thông tin (1..i)]).

Lưu ý:

- Binary Indexed Tree cũng có thể áp dụng đối với 1 tập hợp không cố định nhưng nếu với thông tin là tìm min/max thì độ phức tạp trong quá trình cập nhật thông tin sẽ

- Vẫn có thể lấy thông tin trong đoạn từ I..J bất kì trong các trường hợp còn lại nhưng với độ phức tạp thuật toán cao hơn 1 chút, cỡ O((logN)^2) như sau:

Dựa vào nhận xét: thông tin lưu tại I là thông tin các nút từ I’+1 tới I (theo định nghĩa I’). Do đó có thể viết 1 function tổng hợp thông tin đơn giản như sau:

Tonghop(i,j)

1. J’=J and (J-1);

2. If (J’+1>=I) tonghop=A[j]+tonghop(I,J’)

3. otherwise tonghop=B[j]+tonghop(I,j-1).

Trong đó B[j] là thông tin “của” J. Đôi khi cách làm này có thể thay thế cho 1 cách làm Interval tree với độ phức tạp O(logN), thời gian chạy cũng không lâu hơn là mấy nhưng code ngắn và đơn giản.

Ta cũng có thể kết hợp “Rời rạc hoá” trong sử dụng Binary Indexed Tree và mở rộng Binary Indexed Tree thành cây 2 chiều. Cách sử dụng “Rời rạc hoá” chắc đã không còn xa lạ nữa, ở đây xin nói thêm về Binary Indexed Tree 2D.

Xét bài toán xử lý trên ma trận M*N.

Chia ma trận M*N thành N dãy con, mỗi dãy con là 1 hàng. Dùng M binary indexed tree để lưu các dãy con này. Đây là tập cây đầu tiên(T1). Giá trị của 1 nút là tổng số các ô nó quản lý. Sau đó sử dụng N binary indexed tree (tập T2) để quản lý M cây trên. Cây thứ I của tập N cây T2 này sẽ quản lý tất cả các nút thứ I của M cây thuộc tập T1.

Khi đó, gặp 1 thao tác thay đổi, quá trình update lần lượt xảy ra trên tập cây T1 rồi tới tập cây T2. Giả sử update tại vị trí (U,V):

Update_BIT2D(u,v)

1. Cập nhật nút V của cây thứ U trong tập T1.

2. Cập nhật cây thứ V trong tập T2, nút bắt đầu là nút U. {qtrình này diễn ra như 1 cây bình thường}

3. t=v+v and (-v). {t=cha[v]}

4. Update_BIT2D(u,t)

END

Quá trình trên thực hiện trong O(logM*logN) vì có thủ tục gọi update cây V trong tập T2.
Còn thao tác tính giá trị HCN trái dưới (1,1) và phải trên (u,v) cũng thực hiện trong O(logM*logN) như sau:

Get2D(u,v)

1. GET+= giá trị nút U của cây thứ V, tập T2

2. v=v-v and (-v).

3. GET+=GET_BIT2D(u,v)

END

Kết quả trả về trong biến GET.

Như vậy: GET(x1,y1,x2,y2) = GET2D(x2,y2) - GET2D(x1,y2) - GET2D(x2,y1) + GET2D(x1,y1).

Trong các bài toán sử dụng cây để lưu giá trị với ý nghĩa khác ta chỉ cần sửa 1 chút trong hàm GET (bước 1) và trong hàm cập nhật cây thuộc tập T2 là được.

Vậy là ta đã biết về cách sử dụng Binary Indexed Tree 2D: hoàn toàn tương tự với cây Binary Indexed Tree bình thường, chỉ khác 1 chút trong quá trình xử lý 2 lớp cây lồng nhau.

Qua những ý trên ta đã thấy được đặc điểm của Binary Indexed Tree. Dựa vào đó cũng có thể thấy: mọi bài toán làm được bằng Binary Indexed Tree đều có thể làm được bằng Interval Tree (nhưng điều ngược lại trong 1 số trường hợp không đúng).

Để hiểu rõ cấu trúc này hơn và quan trọng là ghi nhớ những công thức đã nêu, sau đây là 1 số bài tập ứng dụng. Sau khi làm bằng Binary Indexed Tree, bạn hãy thử làm với Interval Tree để so sánh tốc độ và độ phức tạp thuật toán.

Bài tập tự giải:

0. The BUS (đã được nêu trong phần bài tập về interval tree)

1. DNT – Marathon 05-06 (IOIcamp.net)

Cho dãy số A1, A2,..., An. Một nghịch thế là 1 cặp số u,v sao cho: uAv.

Yêu cầu: đếm số lượng nghịch thế của dãy số đã cho.

Input: Dòng đầu tiên ghi số N là số lượng số của dãy số. N dòng tiếp theo lần lượt ghi giá trị của các số thuộc dãy.

Output: 1 số duy nhất là số lượng nghịch thế đếm được.

Giới hạn:

- 1<=N<=60000

- 0

2. MOBILE PHONES - IOI 2001.

Giả thiết một thế hệ thứ 4 điện thoại di động (mobile phone) có các trạm làm việc nằm trong vùng Tamperehoạt động như sau: Vùng hoạt động này được chia theo lưới ô vuông. Các ô vuông tạo thành một ma trận SxS với các hàng và cột được đánh số từ 0 đến S-1. Mỗi ô vuông chứa một trạm làm việc. Số lượng các điện thoại đang hoạt động (active) trong một ô vuông sẽ bị thay đổi khi người sử dụng điện thoại di chuyển từ ô này sang ô khác hoặc điện thoại chuyển chế độ bật/tắt. Theo thời gian, mỗi trạm làm việc sẽ báo cáo sự thay đổi số lượng điện thoại di động đang hoạt động trong khu vực kiểm soát của mình.

Hãy viết chương trìnhnhận các báo cáo đó và trả lời được các yêu cầu về tổng số điện thoại di động đang hoạt động trong một vùng không gian hình vuông cho trước.

Input:

Dòng đầu tiên ghi 0 S là kích thước bảng.

Trong 1 số dòng sau, mỗi dòng thuộc 1 trong 3 dạng sau:

- 1 X Y A : tăng thêm lượng A vào số điện thoại hoạt động trong ô vuông (x,y). A có thể là số âm

- 2 L B R T : yêu cầu cho biết tổng số lượng máy điện thoai hoạt động trong vùng HCN góc trái dưới (L,B) và phải trên (R,T).

3. TEAM SELECTION – Balkan OI 2004.

Trong 1 cuộc thi lớn có N thí sinh tham gia. Cuộc thi này gồm 3 phần thi nhỏ. Tất cả N thí sinh đều tham gia và có điểm số ở cả 3 phần thi này, điểm số 2 thí sinh khác nhau trong 1 phần thi là khác nhau. Sau khi cuộc thi kết thúc, BTC muốn tìm ra các thí sinh giỏi nhất. Thí sinh giỏi nhất là thí sinh không kém hơn bất kì thí sinh nào khác. (Thí sinh A được coi là giỏi hơn thí sinh B nếu điểm số cả 3 phần thi đều cao hơn thí sinh B).

Yêu cầu: cho biết điểm 3 phần thi của N thí sinh, đếm số thí sinh được coi là giỏi nhất trong kì thi trên.

Input: dòng đầu tiên ghi số N là số thí sinh tham dự. N dòng tiếp theo dòng thứ I ghi 3 số nguyên là điểm từng môn thi của thí sinh thứ I.

Output: 1 dòng duy nhất ghi kết quả tìm được.

Giới hạn: N<=10000, điểm thi <= 10^9.

(Còn tiếp)

Đoàn Mạnh Hùng

School@net (Theo THNT)