Hướng giải của Cây Phân Đoạn Động

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Hướng dẫn giải

Bài toán yêu cầu quản lý khoảng chỉ số cực lớn (\(10^9\)). Để tránh lỗi tràn bộ nhớ, ta sử dụng Cây phân đoạn động (Dynamic Segment Tree):

  • Ta không khởi tạo trước toàn bộ cây nhị phân đầy đủ.
  • Mỗi node ban đầu chỉ được tạo khi thực hiện thao tác cập nhật đi qua node đó.
  • Cấu trúc node lưu thêm hai con trỏ hoặc chỉ số left và right để liên kết tới node con tương ứng nếu được khởi tạo.

Độ phức tạp bộ nhớ tối đa là \(O(Q \log (\text{MAX}))\), tối ưu hơn rất nhiều so với mảng tĩnh \(4 \cdot 10^9\).

Mã nguồn C++ mẫu

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

struct Node {
    long long sum;
    int left, right;
};

vector<Node> tree;

int create_node() {
    tree.push_back({0, -1, -1});
    return tree.size() - 1;
}

void update(int node, int start, int end, int pos, long long val) {
    if (start == end) { tree[node].sum = val; return; }
    int mid = start + (end - start)/2;
    if (pos <= mid) {
        if (tree[node].left == -1) { int id = create_node(); tree[node].left = id; }
        update(tree[node].left, start, mid, pos, val);
    } else {
        if (tree[node].right == -1) { int id = create_node(); tree[node].right = id; }
        update(tree[node].right, mid+1, end, pos, val);
    }
    long long l_sum = (tree[node].left != -1) ? tree[tree[node].left].sum : 0;
    long long r_sum = (tree[node].right != -1) ? tree[tree[node].right].sum : 0;
    tree[node].sum = l_sum + r_sum;
}

long long query(int node, int start, int end, int l, int r) {
    if (node == -1 || r < start || end < l) return 0;
    if (l <= start && end <= r) return tree[node].sum;
    int mid = start + (end - start)/2;
    return query(tree[node].left, start, mid, l, r) + query(tree[node].right, mid+1, end, l, r);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int q; if (!(cin >> q)) return 0;
    create_node(); // root node at index 0
    int root = 0;
    int max_val = 1e9;
    while (q--) {
        int t; cin >> t;
        if (t == 1) { int pos; long long val; cin >> pos >> val; update(root, 1, max_val, pos, val); }
        else { int l, r; cin >> l >> r; cout << query(root, 1, max_val, l, r) << "\n"; }
    }
}

Nhận xét

Không có ý kiến tại thời điểm này.