Giới Thiệu Fenwick Tree

Fenwick Tree (Cây chỉ nhị phân) là cấu trúc dữ liệu hỗ trợ cập nhật điểm và truy vấn tổng tiền tố với độ phức tạp O(log n). Ưu điểm bao gồm mã ngắn và hằng số nhỏ.

Nguyên Lý Hoạt Động

Dựa trên khái niệm lowbit - giá trị bit thấp nhất của số. Ví dụ: lowbit(6) = 2 (nhị phân 110), tính bằng x & -x. Mỗi nút tree[i] lưu tổng đoạn [i - lowbit(i) + 1, i]. Mọi tổng tiền tố có thể biểu diễn bằng tối đa log(n) đoạn.

Cập Nhật Điểm

void update(int pos, int val) {
    while (pos <= n) {
        fenw[pos] += val;
        pos += pos & -pos;
    }
}

Truy Vấn Tổng Tiền Tố

int query_prefix(int pos) {
    int res = 0;
    while (pos) {
        res += fenw[pos];
        pos -= pos & -pos;
    }
    return res;
}

Ứng Dụng Điển Hình

Đếm Cặp Nghịch Thế

long long count_inversions(vector<int>& arr) {
    long long cnt = 0;
    for (int i = 0; i < arr.size(); i++) {
        cnt += query_prefix(n) - query_prefix(arr[i]);
        update(arr[i], 1);
    }
    return cnt;
}

Cập Nhật Đoạn - Truy Vấn Điểm

Sử dụng mảng hiệu diff:

void range_update(int l, int r, int delta) {
    update(l, delta);
    update(r + 1, -delta);
}

int point_query(int pos) {
    return query_prefix(pos);
}

Truy Vấn Tổng Đoạn

Sử dụng hai cây Fenwick:

void build_diff(int arr[]) {
    for (int i = 1; i <= n; i++) {
        fenw1[i] += arr[i] - arr[i-1];
        fenw2[i] = fenw1[i] * i;
    }
}

int range_sum(int l, int r) {
    return (r + 1) * query_prefix(fenw1, r) 
         - query_prefix(fenw2, r) 
         - l * query_prefix(fenw1, l - 1) 
         + query_prefix(fenw2, l - 1);
}

Tìm Phần Tử Thứ K

int kth_element(int k) {
    int pos = 0, sum = 0;
    for (int i = 20; i >= 0; i--) {
        if (pos + (1 << i) > max_val) continue;
        if (sum + fenw[pos + (1 << i)] < k) {
            sum += fenw[pos + (1 << i)];
            pos += (1 << i);
        }
    }
    return pos + 1;
}

Bài Toán Minh Họa

E. Trung Vị Trực Tuyến

Ý tưởng: Dùng Fenwick Tree lưu tần suất, tìm vị trí đầu tiên có tần suất tích lũy > n/2.

F. Tính Tổng Khoảng Cách

Ý tưởng: Sắp xếp theo tọa độ, duyệt hai chiều kết hợp hai Fenwick Tree (lưu số lượng và tổng tọa độ).

J. XOR Chẵn Lần

Ý tưởng: Kết hợp prefix XOR và Fenwick Tree offline để tính XOR các phần tử riêng biệt.