Tác giả: Nguyễn RR Thành Trung
Persistent Data Structures là những cấu trúc dữ liệu được dùng khi chúng ta cần có toàn bộ lịch sử của các thay đổi trên 1 cấu trúc dữ liệu (CTDL). (Chú ý rằng từ persistent còn được dùng trong persistent storage với một nghĩa hoàn toàn khác).
Xét bài toán ví dụ:
Nếu không có đoạn tại thời điểm sau phép gán thứ K, bài toán là 1 bài cơ bản trên Interval Tree. Đoạn tại thời điểm sau phép gán thứ K buộc chúng ta phải lưu lại các thông tin về lịch sử cập nhật CTDL - việc này được giải quyết bằng các Persistent Data Structures.
Gọi trạng thái của CTDL tại một thời điểm là 1 version của CTDL đó. Một cách cụ thể hơn, persistent data structures cho phép chúng ta:
Trong một số cách cài đặt, Persistent Data Structures còn có thể cho phép thay version hiện tại của CTDL thành một version trong quá khứ (phần 2 mô tả phương pháp cài đặt có thể thực hiện được thao tác này).
Cần hiểu rằng Persistent Data Structures không phải là một loại CTDL mới. Nó là một số kĩ năng tổng quát giúp thêm thông tin về lịch sử thay đổi vào CTDL thông thường một cách hiệu quả. Ví dụ:
Tại sao lại là một cách hiệu quả? Bởi vì ta hoàn toàn có thể có một Persistent Data Structures bằng cách trâu bò: khi cập nhật, ta tạo một bản sao hoàn toàn mới của CTDL, thay đổi một số dữ liệu trên nó và lưu lại. Như vậy ta luôn có được một thuật toán với độ phức tạp và bộ nhớ , với là số thao tác cần thực hiện, và là độ lớn của CTDL, và là thời gian để thực hiện thao tác trên CTDL.
Trong các phần dưới đây, mình sẽ trình bày về 2 kĩ thuật thông thường của Persistent Data Structures.
Quay trở lại bài toán. Chúng ta biết rằng mỗi thao tác update trên IT chỉ mất . Điều này tương đương với việc mỗi thao tác update chỉ làm thay đổi nút trên cây. Như vậy ta hoàn toàn có thể lưu lại tất cả các thay đổi trên tất cả các nút trong .
Từ đó, ta rút ra được một tư tưởng cài đặt thuật toán:
Với mỗi thao tác Update, ta tạo thêm một số nút mới trên IT. Để không phải sinh thêm các nút không bị thay đổi, một nút ở version mới có thể có con là một nút ở vesion cũ.
Chú ý: Mỗi thao tác Update luôn thay đổi một đường đi từ gốc đến một nút lá, nên không có trường hợp một nút ở version cũ có con là một nút ở version mới hơn. (Nếu thao tác Update là Update 1 đoạn, các nút bị thay đổi không còn là một đường đi nữa, nhưng nhận xét này vẫn đúng).
Khi thực hiện thao tác Query trên version t, ta chỉ cần thực hiện Query trên nút gốc ở version t.
Tư tưởng này còn được gọi là Path Copy trong các tài liệu tiếng Anh.
struct Node {
int left, right; // ID of left child & right child
long long ln; // Max value of node
Node() {}
Node(long long ln, int left, int right) : ln(ln), left(left), right(right) {}
} it[11000111]; // Each node has a position in this array, called ID
int nNode;
int ver[MN]; // ID of root in each version
// Update max value of a node
inline void refine(int cur) {
it[cur].ln = max(it[it[cur].left].ln, it[it[cur].right].ln);
}
// Update a range, and return new ID of node
int update(int l, int r, int u, int x, int oldId) {
if (l == r) {
++nNode;
it[nNode] = Node(x, 0, 0);
return nNode;
}
int mid = (l + r) >> 1;
int cur = ++nNode;
if (u <= mid) {
it[cur].left = update(l, mid, u, x, it[oldId].left);
it[cur].right = it[oldId].right;
refine(cur);
}
else {
it[cur].left = it[oldId].left;
it[cur].right = update(mid+1, r, u, x, it[oldId].right);
refine(cur);
}
return cur;
}
// Get max of range. Same as usual IT
int get(int nodeId, int l, int r, int u, int v) {
if (v < l || r < u) return -1;
if (u <= l && r <= v) return it[nodeId].ln;
int mid = (l + r) >> 1;
return max(get(it[nodeId].left, l, mid, u, v), get(it[nodeId].right, mid+1, r, u, v));
}
// When update:
++nVer;
ver[nVer] = update(1, n, u, x, ver[nVer-1]);
// When query:
res = get(ver[t], 1, n, u, v);
Giải thích:
left và right)lnverupdate:
get:
nodeIdTại mỗi nút của BIT, thay vì lưu một giá trị, ta lưu lại tất cả các cặp (version, giá trị) ở nút đó.
Cách cài đặt này được gọi là Fat Node trong các tài liệu tiếng Anh.
Code BIT trích từ bài IPSC 2011 - Grid Surveillance:
#define _(x) (x & (-(x)))
// Persistent BIT
vector< pair<int,int> > bit[4100][4100];
// Add val to cell (x, y) at time = time
void update(int x, int y, int val, int time) {
for(int u = x; u <= 4096; u += _(u))
for(int v = y; v <= 4096; v += _(v)) {
if (bit[u][v].empty()) {
bit[u][v].push_back(make_pair(time, val));
}
else {
int cur = bit[u][v][bit[u][v].size()-1].second;
bit[u][v].push_back(make_pair(time, cur + val));
}
}
}
// Get the sum of square (1,1) --> (x, y) at time = time
int get(int time, int x, int y) {
int res = 0;
for(int u = x; u > 0; u -= _(u))
for(int v = y; v > 0; v -= _(v)) {
if (bit[u][v].empty()) {
}
else if (bit[u][v][bit[u][v].size()-1].first <= time) {
res += bit[u][v][bit[u][v].size()-1].second;
}
else {
int pos = upper_bound(bit[u][v].begin(), bit[u][v].end(), make_pair(time, 2000111000))
- bit[u][v].begin() - 1;
if (pos >= 0)
res += bit[u][v][pos].second;
}
}
return res;
}
Một lớp CTDL khác tương đối giống với Persistent Data Structures, nhưng có tính ứng dụng thực tế cao hơn là Retroactive Data Structures:
"Retroactive Data Structures là loại CTDL cho phép thực hiện thay đổi với một dãy các thao tác đã được thực hiện trên dữ liệu. Ví dụ: Thay đổi một thao tác đã được thực hiện trong quá khứ".
Cả Retroactive Data Structures & Persistent Data Structures đều quan tâm đến trục thời gian, tuy nhiên điểm khác nhau nằm ở chỗ cách xử lý trục thời gian của 2 CTDL này như thế nào:
Sự khác biệt về cách xử lý trục thời gian khiến cho Retroactive Data Structures có rất nhiều ứng dụng trên thực tế - trái ngược hẳn với Persistent Data Structures chỉ thường được thấy ở trong các kỳ thi. Một vài ứng dụng quan trọng của Retroactive Data Structures gồm có:
Trên thực tế, Retroactive Data Structures còn đang dừng lại ở việc là một khái niệm, chứ chưa có một phương pháp cài đặt nào hiệu quả. Các bạn nếu muốn tìm hiểu có thể nghiên cứu thêm về cơ chế rollback trong database hoặc tìm kiếm thêm về Retroactive Data Structures.