Trong bài toán tìm kiếm phần tử trên đoạn thẳng (Range Search) hoặc tính tổng đoạn, tư tưởng Divide and Conquer được thể hiện như thế nào trong cấu trúc dữ liệu Fenwick Tree (Binary Indexed Tree)?

Question

Accepted Answer

Tư tưởng chia để trị ẩn trong Fenwick Tree
Fenwick Tree biểu diễn một mảng tuyến tính thông qua các khoảng tổng dựa trên hệ cơ số 2 (Binary Representation). Thay vì chia đôi mảng một cách đối xứng như Merge Sort hay Binary Search, Fenwick Tree chia mảng thành các đoạn có kích thước tương ứng với giá trị của bit 1 thấp nhất (Lowest Set Bit - LSB).
Cơ chế hoạt động

Mỗi phần tử tại vị trí i trong Fenwick Tree lưu tổng của một đoạn có độ dài tương ứng với i & (-i).
Khi thực hiện truy vấn tổng từ 1 đến i (Query), bài toán được chia nhỏ thành việc cộng dồn các giá trị của các đoạn không giao nhau bằng cách liên tục trừ đi bit LSB (i -= i & (-i)).
Khi cập nhật dữ liệu (Update), ta cũng áp dụng nguyên lý ngược lại bằng cách cộng thêm bit LSB (i += i & (-i)) để lan truyền sự thay đổi qua các đoạn chứa phần tử đó.

Đánh giá hiệu năng và ứng dụng thực tế

Độ phức tạp: Cả hai thao tác Update và Query đều đạt O(log n).
Ưu điểm so với Segment Tree: Cài đặt cực kỳ ngắn gọn, tốn ít bộ nhớ hơn vì không cần cây con trỏ phức tạp, rất phù hợp cho các hệ thống Enterprise cần xử lý thống kê tần suất thời gian thực (Real-time analytics) với dung lượng dữ liệu lớn.

Trong bài toán tìm kiếm phần tử trên đoạn thẳng (Range Search) hoặc tính tổng đoạn, tư tưởng Divide and Conquer được thể hiện như thế nào trong cấu trúc dữ liệu Fenwick Tree (Binary Indexed Tree)?

Tư tưởng chia để trị ẩn trong Fenwick Tree

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 divide & conquer liên quan cùng chủ đề