Problem statement

https://binarysearch.com/problems/Virtual-Array/

Solution

Variation of Leetcode 0715 Range Module, here we again can use sorted containters.

Complexity

It is O(log n) for set and get for time. Space is O(n).

Code

class VirtualArray:
    def __init__(self):
        self.ranges = SortedList()

    def rangeHelper(self, left, right, bit):
        start = SortedList.bisect_left(self.ranges, left)
        end = SortedList.bisect_right(self.ranges, right)
        for _ in range(end - start): self.ranges.pop(start)
        if start % 2 == bit: self.ranges.add(left)
        if end % 2 == bit: self.ranges.add(right)
        
    def set(self, left, right):
        self.rangeHelper(left, right + 1, 0)

    def get(self, idx):
        start = SortedList.bisect_right(self.ranges, idx)	
        return start % 2 == 1

Remark

Or we can use segment tree with lazy updates.