Snapshot array¶
Copying the entire array on every snapshot costs O(length × snapshots) even
when few indices change. Store only changes.
Ownership model¶
- The outer array owns one history per index.
- Each history stores sorted
(snapshot_id, value)changes. - A global counter owns the next snapshot ID.
- Binary search finds the last change whose ID is not after the query.
Initialize each history with (0, 0) so every query has a valid predecessor.
Update blueprint¶
set(index, value):
history = versions[index]
if history.last.snapshot_id == current_snapshot:
history.last.value = value # coalesce writes in one version
else:
history.append(current_snapshot, value)
snap():
returned = current_snapshot
current_snapshot += 1
return returned
get(index, snapshot):
return value at upper_bound(snapshot) - 1 # newest visible change
Invariant: each index history has strictly increasing snapshot IDs after coalescing, and its final entry is the current value for that index.
flowchart LR
accTitle: Snapshot array finds the newest version visible to a query
accDescr: An index history contains changes at snapshots zero, two, and five. A get at snapshot three searches to the first later entry at five, steps back, and returns the value from snapshot two.
H["History for one index<br/>(0,5) → (2,9) → (5,4)"] --> Q["get(index, snapshot 3)"]
Q --> U["upper_bound finds<br/>first ID greater than 3: ID 5"]
U --> P["Step back once<br/>newest ID at most 3: ID 2"]
P --> R["Return value 9"]The search is for a predecessor, not necessarily an exact version. Ask which change was most recent as of the requested snapshot.
Complexity and traps¶
- Set:
O(1)amortized. - Snap:
O(1). - Get:
O(log changes_at_index). - Space:
O(length + successful version changes). - Coalesce repeated writes before the next snapshot.
- Validate index and snapshot ranges.
- Distinguish the current in-progress version from the last returned snapshot.
Practice¶
Tested template¶
class SnapshotArray:
"""Store sparse per-index histories instead of copying every snapshot."""
def __init__(self, length: int) -> None:
if length < 0:
raise ValueError("length must be nonnegative")
self.current_snapshot = 0
self.history = [[(0, 0)] for _ in range(length)]
def set(self, index: int, value: int) -> None:
if not 0 <= index < len(self.history):
raise IndexError("index outside snapshot array")
entries = self.history[index]
if entries[-1][0] == self.current_snapshot:
# Coalesce repeated writes in the current in-progress version.
entries[-1] = (self.current_snapshot, value)
else:
entries.append((self.current_snapshot, value))
def snap(self) -> int:
snapshot = self.current_snapshot
self.current_snapshot += 1
return snapshot
def get(self, index: int, snapshot: int) -> int:
if not 0 <= index < len(self.history):
raise IndexError("index outside snapshot array")
if not 0 <= snapshot < self.current_snapshot:
raise ValueError("snapshot has not been created")
entries = self.history[index]
# Right-bias finds the newest entry whose snapshot is not later.
position = bisect_right(entries, (snapshot, float("inf"))) - 1
return entries[position][1]
class SnapshotArray {
public:
explicit SnapshotArray(int length) {
if (length < 0) {
throw std::invalid_argument("length must be nonnegative");
}
history_.assign(static_cast<std::size_t>(length),
std::vector<std::pair<int, int>>(1, {0, 0}));
}
void set(int index, int value) {
require_index(index);
auto& entries = history_[index];
if (entries.back().first == current_snapshot_) {
// Coalesce repeated writes in the current in-progress version.
entries.back().second = value;
} else {
entries.push_back({current_snapshot_, value});
}
}
int snap() { return current_snapshot_++; }
int get(int index, int snapshot) const {
require_index(index);
if (snapshot < 0 || snapshot >= current_snapshot_) {
throw std::invalid_argument("snapshot has not been created");
}
const auto& entries = history_[index];
// upper_bound(snapshot) - 1 is the newest visible change.
const auto after = std::upper_bound(
entries.begin(), entries.end(), snapshot,
[](int query, const std::pair<int, int>& entry) {
return query < entry.first;
});
return std::prev(after)->second;
}
private:
void require_index(int index) const {
if (index < 0 || index >= static_cast<int>(history_.size())) {
throw std::out_of_range("index outside snapshot array");
}
}
int current_snapshot_ = 0;
std::vector<std::vector<std::pair<int, int>>> history_;
};
class SnapshotArray {
public:
explicit SnapshotArray(int length) {
if (length < 0) {
throw std::invalid_argument("length must be nonnegative");
}
history_.assign(static_cast<std::size_t>(length),
std::vector<std::pair<int, int>>(1, {0, 0}));
}
void set(int index, int value) {
require_index(index);
auto& entries = history_[index];
if (entries.back().first == current_snapshot_) {
// Coalesce repeated writes in the current in-progress version.
entries.back().second = value;
} else {
entries.push_back({current_snapshot_, value});
}
}
int snap() { return current_snapshot_++; }
int get(int index, int snapshot) const {
require_index(index);
if (snapshot < 0 || snapshot >= current_snapshot_) {
throw std::invalid_argument("snapshot has not been created");
}
const auto& entries = history_[index];
// upper_bound(snapshot) - 1 is the newest visible change.
const auto after = std::upper_bound(
entries.begin(), entries.end(), snapshot,
[](int query, const std::pair<int, int>& entry) {
return query < entry.first;
});
return std::prev(after)->second;
}
private:
void require_index(int index) const {
if (index < 0 || index >= static_cast<int>(history_.size())) {
throw std::out_of_range("index outside snapshot array");
}
}
int current_snapshot_ = 0;
std::vector<std::vector<std::pair<int, int>>> history_;
};
Repeated writes before snap() coalesce into one history entry. get()
right-biases its search to the newest version not after the query.