Thắc mắc về cây BIT (Binary Indexed Tree)

[hockotg (Moon Cactus)]

Kí hiệu Binary Indexed Trees là BIT. Giả sử có các đối tượng i với i=1… MaxVal , gọi f[i] là tần số xuất hiện đối tượng i , tree[i] là giá trị gắn cho nút có chỉ số i trên cây BIT. Khởi trị: f[0]=0, tree[0]=0. Xét ví dụ cho bảng tần số f ứng với các đối tượng có chỉ số i như bảng sau :

i	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
f[i]	1	0	2	1	1	3	0	4	2	5	2	2	3	1	0	2

có cao nhân nào chỉ cho em tại sao lại có tần số như thế này đc ko ạ em đọc mà chẳng hiểu gì cả

[rogp10]

Bảng này ko phải là BIT tree từ nó ta dựng BIT tree.

Ứng dụng trực tiếp: https://en.wikipedia.org/wiki/Arithmetic_coding vì vậy hay có từ “frequency” khi nhắc đến cái tree này.