Giới thiệu về Cây Fenwick (Binary Indexed Tree)

Cây Fenwick, hay BIT (Binary Indexed Tree), là một cấu trúc dữ liệu giúp giải quyết hiệu quả các vấn đề truy vấn và tích tụ (prefix sum) trong mảng một chiều. Nó được phát minh bởi Peter M. Fenwick vào năm 1994 và được sử dụng rộng rãi trong các ứng dụng yêu cầu tính toán nhanh chóng trên dãy số.

Sự ra đời của Cây Fenwick

Cây Fenwick ra đời để giải quyết vấn đề cơ bản trong việc tính tổng các phần tử của một đoạn liên tục trong mảng một chiều. Trước đây, phương pháp duyệt qua từng phần tử và tính tổng dẫn đến độ phức tạp O(n) cho mỗi truy vấn. Cây Fenwick giảm độ phức tạp này xuống O(log n), làm tăng đáng kể hiệu suất tính toán.

Ưu Điểm và Nhược Điểm của Cây Fenwick

Ưu Điểm

Tính Linh Hoạt: Hỗ trợ cả cập nhật giá trị và tính tổng của một đoạn cụ thể.
Thời Gian Thực Hiện Tốt: Thời gian trung bình O(log n) cho mỗi truy vấn, làm cho cây Fenwick hiệu quả trong các bài toán yêu cầu tính toán liên tục.

Nhược Điểm

Phụ Thuộc vào Bản Chất Cụ Thể Của Bài Toán: Hiệu suất của cây Fenwick phụ thuộc vào tính chất của bài toán, có thể không hiệu quả đối với một số vấn đề khác.
Khó Khăn Ban Đầu Trong Việc Hiểu và Triển Khai: Có thể đòi hỏi sự hiểu biết sâu rộng về cách cây Fenwick hoạt động để sử dụng nó một cách hiệu quả.

Ứng Dụng Thực Tế Của Cây Fenwick

Tối Ưu Hóa Các Phép Tính Toán Trong Cơ Sở Dữ Liệu: Cây Fenwick thường được sử dụng để tối ưu hóa tính toán tổng trên các trường số của các bảng trong cơ sở dữ liệu.
Tìm Kiếm Phần Tử Lớn Thứ K Trong Mảng: Cây Fenwick có thể giải quyết bài toán tìm kiếm phần tử lớn thứ k trong mảng một cách hiệu quả.
Tính Toán Tổng Số Lượng Các Số Nhỏ Hơn Một Giá Trị Cho Trước: Với tính chất tích tụ, cây Fenwick là một lựa chọn tốt cho việc đếm số lượng phần tử nhỏ hơn một giá trị cụ thể trong mảng.

Triển khai Cây Fenwick trên C++

#include <iostream>
#include <vector>

using namespace std;

class FenwickTree {
private:
    vector<int> BIT;
    int n;

public:
    FenwickTree(int size) {
        n = size;
        BIT.assign(n + 1, 0);
    }

    void update(int idx, int val) {
        for (; idx <= n; idx += idx & -idx)
            BIT[idx] += val;
    }

    int query(int idx) {
        int sum = 0;
        for (; idx > 0; idx -= idx & -idx)
            sum += BIT[idx];
        return sum;
    }
};

Sử dụng Cây Fenwick trong Javascript

class FenwickTree {
  constructor(size) {
    this.BIT = new Array(size + 1).fill(0);
    this.n = size;
  }

  update(idx, val) {
    for (; idx <= this.n; idx += idx & -idx) {
      this.BIT[idx] += val;
    }
  }

  query(idx) {
    let sum = 0;
    for (; idx > 0; idx -= idx & -idx) {
      sum += this.BIT[idx];
    }
    return sum;
  }
}

Cây Fenwick trong Python

class FenwickTree:
    def __init__(self, size):
        self.BIT = [0] * (size + 1)
        self.n = size

    def update(self, idx, val):
        while idx <= self.n:
            self.BIT[idx] += val
            idx += idx & -idx

    def query(self, idx):
        sum_val = 0
        while idx > 0:
            sum_val += self.BIT[idx]
            idx -= idx & -idx
        return sum_val

Cây Fenwick là một công cụ mạnh mẽ giúp giải quyết các vấn đề tích tụ một cách hiệu quả. Bài viết này đã giới thiệu triển khai cơ bản của cây Fenwick trên C++, Javascript, và Python, giúp bạn dễ dàng tích hợp nó vào các dự án của mình.

Kết Luận

Cây Fenwick không chỉ là một công cụ hiệu quả cho các vấn đề tích tụ mà còn là một ví dụ xuất sắc về sự kết hợp giữa tính linh hoạt và hiệu suất. Để sử dụng cây Fenwick một cách hiệu quả, hiểu rõ về cách nó hoạt động và áp dụng nó vào các bài toán cụ thể là chìa khóa.