Binary Indexed Tree

1. Giới thiệu về Cây Fenwick

1.1 Định nghĩa của Cây Fenwick

Cây Fenwick (Binary Indexed Tree): Cũng được gọi là cây Fenwick do người phát minh ra nó là Peter M. Fenwick vào năm 1994 với bài viết có tiêu đề “A New Data Structure for Cumulative Frequency Tables” trên SOFTWARE PRACTICE AND EXPERIENCE. Ban đầu, nó được thiết kế để giải quyết vấn đề tính toán tần suất tích lũy (Cumulative Frequency) trong nén dữ liệu, nhưng hiện nay nó được sử dụng rộng rãi để tính tổng tiền tố và tổng trong một dãy số. Nó có thể tính tổng của bất kỳ tiền tố ${\sum }_{i=1}^{j}A[i],1\le j\le n$ trong thời gian $O(\log n)$ và cũng hỗ trợ việc thay đổi giá trị của một điểm động trong thời gian $O(\log n)$. Không gian lưu trữ của cây Fenwick là $O(n)$.

1.2 Nguyên lý hoạt động của Cây Fenwick

2. Các hoạt động cơ bản của Cây Fenwick

2.1 Xây dựng Cây Fenwick

2.2 Sửa đổi giá trị trong Cây Fenwick

2.3 Tính tổng trong Cây Fenwick

4. Các loại bài toán phổ biến sử dụng Cây Fenwick

4.1 Cập nhật điểm + Tính tổng trong khoảng

4.2 Cập nhật khoảng + Tính tổng điểm

4.3 Tính số cặp nghịch thế