1146. Snapshot Array - LeetCode

class SnapshotArray:
    def __init__(self, length: int):
        self._array: list[list[tuple[int, int]]] = [[(-1, 0)] for _ in range(length)]
        self._snap_id = -1

    def set(self, index: int, val: int) -> None:
        self._array[index].append((self._snap_id, val))

    def snap(self) -> int:
        self._snap_id += 1
        return self._snap_id

    @staticmethod
    def bs_r(a, t):
        l, r = 0, len(a)
        while l < r:
            m = (l + r) // 2
            if a[m] > t:
                r = m
            else:
                l = m + 1
        return l

    def get(self, index: int, snap_id: int) -> int:
        low = self.bs_r(self._array[index], (snap_id,))
        return self._array[index][low - 1][1]