Snapshot Array: Cấu Trúc Dữ Liệu Hỗ Trợ Chụp Ảnh (Snapshot) Mảng Tại Thời Điểm Khác Nhau

Đề bài: Triển khai SnapshotArray hỗ trợ:

• SnapshotArray(length): Khởi tạo mảng độ dài length, giá trị ban đầu 0.
• set(index, val): Gán arr[index] = val tại snapshot hiện tại.
• snap(): Chụp snapshot, trả về snap_id (số lần snap đã gọi - 1).
• get(index, snap_id): Lấy giá trị tại index ở snapshot snap_id.

Ví dụ: set(0,5) → snap()=0 → set(0,6) → get(0,0)=5.

Ý tưởng: Lưu lịch sử thay đổi mỗi index

Mỗi index lưu list [(snap_id, value), ...] đã sort theo snap_id. get dùng binary search tìm snap_id lớn nhất ≤ snap_id truy vấn.

Code Python

class SnapshotArray:
    def __init__(self, length: int):
        self.current_snap = 0
        # Mỗi index: list các (snap_id, value), khởi tạo với (0, 0)
        self.history = [[(0, 0)] for _ in range(length)]
    
    def set(self, index: int, val: int) -> None:
        # Nếu snap_id hiện tại trùng entry cuối → cập nhật value
        if self.history[index][-1][0] == self.current_snap:
            self.history[index][-1] = (self.current_snap, val)
        else:
            self.history[index].append((self.current_snap, val))
    
    def snap(self) -> int:
        snap_id = self.current_snap
        self.current_snap += 1
        return snap_id
    
    def get(self, index: int, snap_id: int) -> int:
        arr = self.history[index]
        # Binary search: tìm entry lớn nhất có snap_id <= snap_id truy vấn
        left, right = 0, len(arr) - 1
        while left < right:
            mid = (left + right + 1) // 2  # upper mid
            if arr[mid][0] <= snap_id:
                left = mid
            else:
                right = mid - 1
        return arr[left][1]

# Test
obj = SnapshotArray(3)
obj.set(0, 5)
print(obj.snap())      # 0
obj.set(0, 6)
print(obj.get(0, 0))   # 5 (giá trị tại snap 0)
print(obj.get(0, 1))   # 6 (giá trị tại snap 1 - current)

Kết quả

0
5
6

Phân tích độ phức tạp

• set: O(1) amortized
• snap: O(1)
• get: O(log S) với S = số snapshot tại index đó
• Space: O(length + số lần set)

So sánh với bản ghi nguyên gốc (bài gốc)

Bài gốc dùng self.arr = [[[0,0]] for _ in range(length+1)] và logic binary search hơi rối. Bản này:

• Khởi tạo [(0,0)] cho mỗi index → không cần xử lý đặc biệt index 0.
• Binary search chuẩn upper-bound, dễ hiểu hơn.
• Tách rõ current_snap và snap_id trả về.

Kết luận

Snapshot Array là pattern "persistent array" dùng history + binary search. Áp dụng cho version control, undo/redo, time-travel debugging.