Binary Indexed Tree (Fenwick Tree) trong C++

So với mảng phẳng, Fenwick Tree (Binary Indexed Tree) cân bằng tốt hơn giữa hai phép toán: cập nhật phần tử và tính tổng tiền tố (prefix sum).

• Mảng phẳng: lưu phần tử → tính tổng tiền tố O(n); lưu tổng tiền tố → cập nhật O(n).
• Fenwick Tree: cả hai phép toán đều O(log m).

Cách hoạt động: biểu diễn số như cây, giá trị nút = tổng các số trong cây con đó. Cấu trúc cây cho phép truy cập O(log m) nút.

Dùng mảng 1-based. Phần tử có chỉ số là lũy thừa của 2 (j = 2^k) lưu tổng j phần tử đầu. Phần tử có chỉ số = tổng hai lũy thừa khác nhau lưu tổng từ lũy thừa trước. Mỗi nút lưu tổng từ nút cha, cha tìm bằng cách xóa bit ít quan trọng nhất (least significant bit) trong chỉ số.

Để tính tổng đến vị trí i: xem dạng nhị phân của i, cộng các phần tử tương ứng với mỗi bit 1.

Ví dụ: tính tổng 11 phần tử đầu. 11 = 1011 (nhị phân) → 3 bit 1 → cộng 3 phần tử: 1000 (8), 1010 (10), 1011 (11) → tương ứng tổng 1-8, 9-10, 11.

Triển khai C đơn giản

#define LSB(i) ((i) & -(i)) // chỉ giữ bit ít quan trọng nhất
int A1[SIZE];

int sum(int i) { // Tổng từ 1 đến i
    int sum = 0;
    while (i > 0)
        sum += A1[i], i -= LSB(i);
    return sum;
}

void add(int i, int k) { // Cộng k vào phần tử chỉ số i
    while (i < SIZE)
        A1[i] += k, i += LSB(i);
}