Virtual Array - Google Top Interview Questions

                        Solution in C++ :

class VirtualArray {
    const long long A = 1LL << 32;
    unordered_map<long long, int> a;

    public:
    VirtualArray() {
    }

    void upd(long long x, int d) {
        ++x;
        while (x < A) a[x] += d, x += x & -x;
    }

    int qry(long long x) {
        ++x;
        int y = 0;
        while (x > 0) y += a[x], x -= x & -x;
        return y;
    }

    void set(int start, int end) {
        upd(start, 1);
        upd(end + 1, -1);
    }

    bool get(int idx) {
        return qry(idx) > 0;
    }
};
                    

                        Solution in Java :

import java.util.*;

class VirtualArray {
    private final TreeMap<Integer, Integer> truth = new TreeMap<>();

    public void set(int start, int end) {
        Map.Entry<Integer, Integer> entry = truth.floorEntry(start);
        {
            if (entry != null && entry.getValue().intValue() >= start) {
                truth.remove(entry.getKey());
                start = Math.min(start, entry.getKey());
                end = Math.max(end, entry.getValue());
            }
        }
        {
            while (true) {
                entry = truth.ceilingEntry(start);
                if (entry == null || entry.getKey().intValue() > end)
                    break;
                truth.remove(entry.getKey());
                end = Math.max(end, entry.getValue());
            }
        }
        truth.put(start, end);
    }

    public boolean get(int idx) {
        Map.Entry<Integer, Integer> entry = truth.floorEntry(idx);
        return (entry != null && entry.getValue() >= idx);
    }
}
                    

                        Solution in Python : 
                            
class VirtualArray:
    __slots__ = "start", "end", "mid", "_left", "_right", "state"

    def __init__(self, start=0, end=2 ** 31):
        self.start = start
        self.end = end
        self.mid = start + end >> 1
        self._left = self._right = None
        self.state = 0

    @property
    def left(self):
        if not self._left:
            self._left = VirtualArray(self.start, self.mid)
        return self._left

    @property
    def right(self):
        if not self._right:
            self._right = VirtualArray(self.mid + 1, self.end)
        return self._right

    def set(self, s, e):
        if s <= self.start and self.end <= e:
            self.state = 1
        elif e <= self.mid:
            self.left.set(s, e)
        elif s > self.mid:
            self.right.set(s, e)
        else:
            self.left.set(s, e)
            self.right.set(s, e)

    def get(self, index):
        if self.state == 1:
            return True
        elif self._left is self._right is None:
            return False
        elif index <= self.mid:
            return self.left.get(index)
        else:
            return self.right.get(index)