Cấu Trúc Cây Phân Đoạn (Segment Tree) & Fenwick Tree (BIT)

1. Bản chất bài toán truy vấn đoạn động (dynamic range queries)

Cho mảng $A$ gồm $N$ phần tử. Cần thực hiện liên tiếp $Q$ thao tác thuộc 2 loại:

1. Cập nhật điểm (Point Update): Thay đổi giá trị $A[i] \gets v$ (hoặc $A[i] \gets A[i] + v$).
2. Truy vấn đoạn (Range Query): Tính tổng $\sum_{k=L}^R A[k]$ hoặc tìm $\min_{k=L}^R A[k]$ / $\max_{k=L}^R A[k]$.

2. Cây fenwick (Binary Indexed Tree — BIT)

2.1. Phép toán ma thuật: lowbit(x) = x & (-x)

Phép toán x & (-x) trích xuất bit $1$ thấp nhất (trọng số nhỏ nhất) của số nguyên $x$.

• Mỗi vị trí $x$ trong mảng bit[x] quản lý tổng của một đoạn con có độ dài đúng bằng lowbit(x) kết thúc tại $x$: $$\text{Đoạn quản lý của } x = (x - \text{lowbit}(x), x]$$

2.2. Hai thao tác cốt lõi siêu tinh gọn (chỉ 5 dòng code)

void update(int x, long long val) {
    for (; x <= n; x += x & -x) bit[x] += val;
}

long long query(int x) { // Tính tổng tiền tố A[1..x]
    long long sum = 0;
    for (; x > 0; x -= x & -x) sum += bit[x];

    return sum;
}

long long range_query(int L, int R) {
    return query(R) - query(L - 1);
}

3. Cây phân đoạn (Segment Tree)

3.1. Cấu trúc cây nhị phân hoàn hảo

• Cây phân đoạn biểu diễn mảng quản lý theo cây nhị phân: Nút gốc $id = 1$ quản lý toàn đoạn $[1, N]$.
• Nút con trái quản lý nửa trái $[L, mid]$ tại vị trí $2 \cdot id$.
• Nút con phải quản lý nửa phải $[mid + 1, R]$ tại vị trí $2 \cdot id + 1$.
• Quy tắc bộ nhớ: Mảng cây Segment Tree cần khai báo $4N$ phần tử để đảm bảo không bị tràn chỉ số khi $N$ không phải là lũy thừa của 2.

3.2. Ưu thế vượt trội của Segment Tree

Khác với Fenwick Tree chủ yếu hỗ trợ phép toán có tính nghịch đảo (như phép cộng tổng), Segment Tree hỗ trợ MỌI PHÉP TOÁN KẾT HỢP (Associative Operations):

• Tìm giá trị nhỏ nhất / lớn nhất trên đoạn (Range Minimum / Maximum Query — RMQ).
• Tìm ước chung lớn nhất trên đoạn ($\text{GCD}(A[L \dots R])$).
• Đếm số lượng phần tử đạt cực đại trên đoạn.

4. Các bẫy lỗi lập trình kinh điển (bug traps)

1. Bẫy quên khai báo mảng Segment Tree kích thước $4N$: * Khai báo tree[2 N] hoặc tree[N] sẽ bị tràn mảng (Out of Bounds) khi $N = 10^5$. Bắt buộc phải khai báo kích thước tối thiểu $4N$ (vector<long long> tree(4 n + 5)).

2. Bẫy chỉ số 0-based của Fenwick Tree (Vòng lặp vô tận): * Trong Fenwick Tree, lowbit(0) = 0 & -0 = 0. Nếu gọi update(0, val) hoặc query(0), vòng lặp $x \gets x + (x \ \& \ -x)$ sẽ biến thành x += 0 và chạy vô tận $\implies$ Time Limit Exceeded! * Bất biến sống còn: Fenwick Tree BẮT BUỘC DÙNG CHỈ SỐ 1-BASED ($x \ge 1$).

3. Bẫy tràn số khi cộng dồn tổng trên cây: * Mảng $N = 10^5$ phần tử có giá trị $10^9 \implies$ Tổng đoạn có thể lên tới $10^{14}$. Mảng tree và bit bắt buộc phải dùng kiểu long long.

5. Mẫu cài đặt chuẩn thi đấu (competitive templates)

Mẫu 1: Cây fenwick (BIT) point update & range sum query

#include <bits/stdc++.h>
using namespace std;

struct FenwickTree {
    int n;
    vector<long long> bit;

    FenwickTree(int n) : n(n), bit(n + 1, 0) {}

    void update(int x, long long val) {
        for (; x <= n; x += x & -x) {
            bit[x] += val;
        }
    }

    long long query(int x) {
        long long sum = 0;
        for (; x > 0; x -= x & -x) {

            sum += bit[x];
        }
        return sum;
    }

    long long queryRange(int l, int r) {
        if (l > r) return 0;

        return query(r) - query(l - 1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    if (!(cin >> n >> q)) return 0;

    if (n <= 0) return 0;

    FenwickTree ft(n);

    for (int i = 1; i <= n; ++i) {
        long long x;
        cin >> x;

        ft.update(i, x);
    }

    while (q--) {
        int type;
        cin >> type;

        if (type == 1) { // Update: A[pos] += val
            int pos;
            long long val;
            cin >> pos >> val;

            ft.update(pos, val);
        } else { // Query: Sum(L..R)
            int l, r;
            cin >> l >> r;

            cout << ft.queryRange(l, r) << "\n";
        }
    }

    return 0;
}

Mẫu 2: Cây phân đoạn (Segment Tree) range minimum query (RMQ)

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;

struct SegmentTree {
    int n;
    vector<long long> tree;

    SegmentTree(int n) : n(n), tree(4 * n + 5, INF) {}

    void build(const vector<long long>& a, int id, int l, int r) {
        if (l == r) {
            tree[id] = a[l];
            return;
        }
        int mid = (l + r) / 2;
        build(a, 2 * id, l, mid);
        build(a, 2 * id + 1, mid + 1, r);
        tree[id] = min(tree[2 * id], tree[2 * id + 1]);
    }

    void update(int id, int l, int r, int pos, long long val) {
        if (l == r) {
            tree[id] = val;
            return;
        }
        int mid = (l + r) / 2;
        if (pos <= mid) {
            update(2 * id, l, mid, pos, val);
        } else {
            update(2 * id + 1, mid + 1, r, pos, val);
        }
        tree[id] = min(tree[2 * id], tree[2 * id + 1]);
    }

    long long query(int id, int l, int r, int u, int v) {
        if (v < l || r < u) return INF; // Ngoài đoạn
        if (u <= l && r <= v) return tree[id]; // Nằm trọn trong đoạn

        int mid = (l + r) / 2;
        return min(query(2 * id, l, mid, u, v),
                   query(2 * id + 1, mid + 1, r, u, v));
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    if (!(cin >> n >> q)) return 0;

    if (n <= 0) return 0;

    vector<long long> a(n + 1);

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];

    }

    SegmentTree st(n);
    st.build(a, 1, 1, n);

    while (q--) {
        int type;
        cin >> type;

        if (type == 1) { // Gán A[pos] = val
            int pos;
            long long val;
            cin >> pos >> val;

            st.update(1, 1, n, pos, val);
        } else { // Tìm Min trong đoạn [L, R]
            int l, r;
            cin >> l >> r;

            cout << st.query(1, 1, n, l, r) << "\n";
        }
    }

    return 0;
}