Cây (BST, Segment Tree, Fenwick Tree)

Wiki › Cấu trúc dữ liệu

huunguyen · Last updated 28, Tháng 3, 2026, 22:45

Cây là đồ thị liên thông không có chu trình với $N$ đỉnh và $N - 1$ cạnh.

Cây nhị phân tìm kiếm (BST)

BST là cây nhị phân với tính chất: mọi node ở cây con trái < node hiện tại < mọi node ở cây con phải.

Trong lập trình thi đấu, thường dùng BST cân bằng có sẵn:

#include <set>
#include <map>

set<int> s;
s.insert(3); s.insert(1); s.insert(4);
cout << *s.begin();      // 1 — nhỏ nhất
cout << *s.rbegin();     // 4 — lớn nhất
s.erase(3);

// lower_bound / upper_bound: O(log N)
auto it = s.lower_bound(2);  // phần tử >= 2

from sortedcontainers import SortedList
sl = SortedList([3, 1, 4])
sl.add(2)
print(sl[0])   # 1
sl.remove(3)

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

Hỗ trợ:

Truy vấn trên đoạn $[l, r]$ : tổng, max, min... — $O (\log N)$
Cập nhật một phần tử — $O (\log N)$

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

    SegTree(int n) : n(n), tree(4*n, 0) {}

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

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

    long long query(int node, int l, int r, int ql, int qr) {
        if (qr < l || r < ql) return 0;
        if (ql <= l && r <= qr) return tree[node];
        int mid = (l + r) / 2;
        return query(2*node, l, mid, ql, qr)
             + query(2*node+1, mid+1, r, ql, qr);
    }
};

SegTree seg(n);
seg.build(a, 1, 0, n-1);
seg.update(1, 0, n-1, i, val);
long long s = seg.query(1, 0, n-1, l, r);

Fenwick Tree (Binary Indexed Tree — BIT)

Đơn giản hơn Segment Tree, hỗ trợ prefix sum và cập nhật điểm — $O (\log N)$ .

struct BIT {
    int n;
    vector<long long> tree;
    BIT(int n) : n(n), tree(n+1, 0) {}

    void update(int i, long long delta) {
        for (; i <= n; i += i & (-i)) tree[i] += delta;
    }

    long long query(int i) {
        long long s = 0;
        for (; i > 0; i -= i & (-i)) s += tree[i];
        return s;
    }

    long long query(int l, int r) { return query(r) - query(l-1); }
};

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

    def update(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)

    def query(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s

So sánh Segment Tree và Fenwick Tree

	Segment Tree	Fenwick Tree
Cài đặt	Phức tạp hơn	Đơn giản hơn
Hỗ trợ	Max, min, sum, lazy propagation	Chủ yếu prefix sum
Bộ nhớ	$O (4 N)$	$O (N)$

Bình luận

Không có bình luận tại thời điểm này.