Fenwick Tree

Cây Fenwick là cấu trúc dữ liệu thao tác trên...

• Mảng

• Cây nhị phân

• Cây cân bằng

• Cây bất kỳ

Lệnh idx & (-idx) dùng để tìm...

• Vị trí số 1 đầu tiên của idx trong dãy nhị phân

• Vị trí số 0 đầu tiên của idx trong dãy nhị phân

• Vị trí số 1 cuối cùng của idx trong dãy nhị phân

• Vị trí số 0 cuối cùng của idx trong dãy nhị phân

Cho mảng [4, 7, 2, 8, 6, 3]. Cây Fenwick của mảng này là:

• [4, 11, 13, 21, 27, 30]

• [4, 11, 2, 21, 6, 9]

• [4, 11, 2, 10, 6, 9]

• [30, 19, 11, 10, 9, 4, 7, 2, 8, 6, 3]

Cho mảng [4, 7, 2, 8, 6, 3]. Để tính tổng tích lũy từ 0 đến 3, cây Fenwick của nó đã phải đi qua những index nào?

• 1, 2, 3

• 1, 2, 3, 4

• 4

• 1, 2, 4

Cho mảng [4, 7, 2, 8, 6, 3]. Index 6 của cây Fenwick này đang giữ giá trị là bao nhiêu?

• 3

• 9

• 30

• 17

Lệnh di chuyển trong hàm tính tổng là:

• idx -= idx & (-idx)

• idx += idx & (-idx)

• idx |= idx & (-idx)

• idx = idx & (-idx)

Cho mảng [4, 7, 2, 8, 6, 3]. Sau khi thực hiện lệnh update(3, 3) thì cây Fenwick của nó trở thành:

• [4, 11, 16, 24, 30, 33]

• [4, 11, 5, 24, 9, 12]

• [4, 11, 5, 21, 6, 9]

• [4, 11, 2, 24, 6, 9]

Cho mảng [4, 7, 2, 8, 6, 3]. Nếu ta thực hiện update(1,3) trên cây Fenwick của nó thì ta sẽ phải đi update lại những index nào?

• 1, 2, 4

• 3, 4

• 1, 3, 5

• 2, 4

Độ phức tạp không gian, tính tổng và cập nhật của cây Fenwick lần lượt là:

• O(N)

  O(NlogN)

  O(NlogN)

• O(2N)

  O(logN)

  O(NlogN)

• O(N)

  O(logN)

  O(logN)

• O(N)

  O(NlogN)

  O(logN)

Những ứng dụng của cây Fenwick

• Xử lý hình ảnh

• Phát triển game

• Nén dữ liệu

• Sinh học tính toán