Trong bài toán xử lý luồng dữ liệu (Data Stream), cấu trúc Fenwick Tree (Binary Indexed Tree) có ưu điểm gì so với Segment Tree về mặt bộ nhớ và độ phức tạp cài đặt?

Question

Accepted Answer

So sánh Fenwick Tree và Segment Tree:

Bộ nhớ: Fenwick Tree chỉ sử dụng một mảng có kích thước bằng với số lượng phần tử (O(n)), trong khi Segment Tree cần mảng có kích thước khoảng 4n.
Độ phức tạp cài đặt: Fenwick Tree sử dụng các phép toán bitwise (như i & (-i)) để di chuyển trong cây, giúp code cực kỳ ngắn gọn và hiệu năng cao hơn do ít chiếm dụng bộ nhớ đệm (Cache-friendly).

Hạn chế:
Fenwick Tree chỉ phù hợp với các bài toán có tính chất kết hợp (Associative) như tính tổng tiền tố (Prefix Sum). Nếu bài toán yêu cầu các truy vấn phức tạp hơn như tìm min/max trên đoạn hoặc các cập nhật không giao hoán, Segment Tree vẫn là lựa chọn bắt buộc.
Ví dụ code minh họa thao tác cập nhật:
void update(int i, int delta) {
    for (; i <= n; i += i & -i) tree[i] += delta;
}

Trong bài toán xử lý luồng dữ liệu (Data Stream), cấu trúc Fenwick Tree (Binary Indexed Tree) có ưu điểm gì so với Segment Tree về mặt bộ nhớ và độ phức tạp cài đặt?

So sánh Fenwick Tree và Segment Tree:

Hạn chế:

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi trees liên quan cùng chủ đề