Fenwick tree

Fenwick tree

Bài toán
Cho dãy số a=(a(1), a(2), ..., a(n)) và nhiều phép truy vấn Sum(l, r) dùng tính tổng dãy con a(l) + a(l+1) + ... + a(r) và truy vấn Update(i, x) để tăng giá trị a(i) lên x giá trị.

Giải pháp Fenwick tree
Giới thiệu:

1. Fenwick tree hay Binary Indexed Tree (BIT) là phương pháp tiền xử lý giúp tính tổng Sum(l, r) và cập nhật Update(i, x) trên dãy số a trong thời gian O(log n). 
2. Lịch sử: Phương pháp Fenwick tree do Pete Fenwickin đề xuất vào năm 1994.
3. Độ phức tạp: Độ phức tạp của phép toán tính tổng dãy con và cập nhật các phần tử của mảng là O(log n)

Ý tưởng Fenwick tree:
Fenwick tree là mảng T[1...n], trong T[i] = tổng các phần tử dãy a thuộc đoạn [(i-2^k)+1, i], trong đó k là vị trí bit 1 nằm bên phải nhất của số nhị phân của biến i.

Bây giờ, chúng ta sẽ trình bày toàn bộ code của Fenwick tree:

void Update(int i, int x) {
    while (i<n) {
        T[i] += x;
        i |= (i + 1);
    }
}

int Sum(int n) {
    int res = 0;
    while (n>= 0) {
        res += data[n];
        n= (n& (n+1)) - 1;
    }
    return res;
}

Ở đây, Sum(i) trả về tổng của các phần tự từ phần tử đầu tiên đến phần tử thứ i. Việc tìm tổng của một đoạn bất kỳ có thể thực hiện bằng truy vấn Sum(right)-Sum(left-1). 

Fenwick tree chuẩn chỉ hỗ trợ cập nhật 1 phần tử tại một thời điểm. Tuy nhiên, chúng ta có thể mở rộng cho việc cập nhật cả một đoạn - câu lệnh cập nhật sẽ phát biểu thành "tăng mỗi giá trị giữa left và right một lượng giá trị". Chúng ta có thể chỉnh sửa cây cho cập nhật như thế trong thời gian O(log n):

void Update(int left, int right, int by) {
    internalUpdate(left, by, -by * (left - 1));
    internalUpdate(right, -by, by * right);
}

void InternalUpdate(int i, int mul, int add) {
    while (i<n) {
        dataMul[i] += mul;
        dataAdd[i] += add;
        i|=(i+ 1);
    }
}

int Query(int i) {
    int mul = 0;
    int add = 0;
    int start = i;
    while (i>= 0) {
        mul += dataMul[i];
        add += dataAdd[i];
        i= (i& (i+ 1)) - 1;
    }
    return mul * start + add;
}