Cây được lập chỉ mục nhị phân hoặc Cây Fenwick trong C ++?

Trong trường hợp so sánh với một mảng số phẳng, cây Fenwick dẫn đến sự cân bằng tốt hơn nhiều giữa hai phép toán:cập nhật phần tử và tính tổng tiền tố. Trong trường hợp một mảng phẳng gồm m số, chúng ta có thể lưu trữ các phần tử hoặc các tổng tiền tố. Trong trường hợp đầu tiên, việc tính tổng tiền tố cần thời gian tuyến tính; trong trường hợp thứ hai, việc sửa đổi hoặc cập nhật các phần tử của mảng cần thời gian tuyến tính (trong cả hai trường hợp, hoạt động khác có thể được thực hiện trong thời gian không đổi). Cây Fenwick cho phép thực hiện cả hai hoạt động trong thời gian O (log m). Điều này có được bằng cách biểu diễn các số dưới dạng cây, trong đó giá trị của mỗi nút được coi là tổng các số trong cây con đó. Cấu trúc cây cho phép các hoạt động được thực hiện chỉ bằng cách sử dụng các quyền truy cập vào nút O (log m).

Bằng cách xem xét mảng một dựa trên, cây Fenwick được hiểu một cách dễ dàng nhất. Mỗi phần tử có chỉ số j là lũy thừa của 2 chứa tổng của j phần tử đầu tiên. Các phần tử có chỉ số cho biết tổng của hai lũy thừa (riêng biệt) của 2 bao gồm tổng của các phần tử kể từ lũy thừa đứng trước là 2. Về cơ bản, mỗi phần tử bao gồm tổng các giá trị kể từ gốc của nó trong cây và phần tử đó là được tìm thấy bằng cách xóa bit tối thiểu hoặc ít quan trọng nhất trong chỉ mục.

Để tính tổng cho bất kỳ vị trí hoặc chỉ số nhất định nào, hãy xem xét sự mở rộng nhị phân của vị trí hoặc chỉ mục và thêm các phần tử tương ứng với mỗi 1 bit ở dạng nhị phân.

Ví dụ, hãy để một người muốn tính tổng của 11 giá trị đầu tiên. Mười một là 1011 trong hệ nhị phân. Điều này bao gồm ba bit 1, vì vậy ba phần tử phải được thêm vào:1000, 1010 và 1011. Các phần tử này bao gồm tổng các giá trị 1-8, 9-10 và 11, tương ứng.

Một triển khai C đơn giản sau đây.

Ví dụ

#define LSB(i) ((i) & -(i)) // zeroes all the bits except the minimum or least significant one
int A1[SIZE];
int sum(int i) // Returns the sum from index 1 to i{
   int sum = 0;
   while (i > 0)
   sum += A1[i], i -= LSB(i);
   return sum;
}
void add(int i, int k) // Adds k to element with index i{
   while (i < SIZE)
   A1[i] += k, i += LSB(i);
}