Hướng giải của Tổng Đoạn Trên Lịch Sử

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 tính tổng đoạn con trên các phiên bản lịch sử khác nhau. Sử dụng Persistent Segment Tree (Cây phân đoạn bền vững):

  • Mỗi lần cập nhật tạo ra một phiên bản mảng mới bằng cách sao chép các node nằm trên đường đi từ gốc đến lá, các node không bị thay đổi sẽ được trỏ trực tiếp từ node mới sang cây con của phiên bản cũ.
  • Duy trì mảng roots để lưu chỉ số node gốc của từng phiên bản.
  • Khi truy vấn tổng trên phiên bản \(V\), ta gọi hàm query bắt đầu từ gốc roots[V].

Độ phức tạp thời gian: \(O(\log N)\) mỗi thao tác.

Mã nguồn C++ mẫu

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

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

class PersistentSegTree {
public:
    vector<Node> tree;
    vector<int> roots;
    int n;
    PersistentSegTree(int size) { n = size; roots.push_back(0); }
    int build(int start, int end, const vector<int>& a) {
        int id = tree.size();
        tree.push_back({0, -1, -1});
        if (start == end) { tree[id].sum = a[start]; return id; }
        int mid = (start + end)/2;
        int l = build(start, mid, a);
        int r = build(mid+1, end, a);
        tree[id].left = l; tree[id].right = r;
        tree[id].sum = tree[l].sum + tree[r].sum;
        return id;
    }
    int update(int prev_id, int start, int end, int pos, long long val) {
        int id = tree.size();
        tree.push_back(tree[prev_id]);
        if (start == end) { tree[id].sum = val; return id; }
        int mid = (start + end)/2;
        if (pos <= mid) tree[id].left = update(tree[prev_id].left, start, mid, pos, val);
        else tree[id].right = update(tree[prev_id].right, mid+1, end, pos, val);
        tree[id].sum = tree[tree[id].left].sum + tree[tree[id].right].sum;
        return id;
    }
    long long query(int node_id, int start, int end, int l, int r) {
        if (r < start || end < l || node_id == -1) return 0;
        if (l <= start && end <= r) return tree[node_id].sum;
        int mid = (start + end)/2;
        return query(tree[node_id].left, start, mid, l, r) + query(tree[node_id].right, mid+1, end, l, r);
    }
};

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, q; if (!(cin >> n >> q)) return 0;
    vector<int> a(n);
    for (int i=0; i<n; i++) cin >> a[i];
    PersistentSegTree pst(n);
    int initial_root = pst.build(0, n-1, a);
    pst.roots[0] = initial_root;
    int curr_ver = 0;
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int pos; long long val; cin >> pos >> val; pos--;
            int root = pst.update(pst.roots[curr_ver], 0, n-1, pos, val);
            pst.roots.push_back(root);
            curr_ver = pst.roots.size() - 1;
        } else if (t == 2) {
            int v, l, r; cin >> v >> l >> r; l--; r--;
            cout << pst.query(pst.roots[v], 0, n-1, l, r) << "\n";
        } else {
            int v; cin >> v;
            curr_ver = v;
        }
    }
}

Nhận xét

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