Range Module — DSA · Engineering Playbook

Problem#

Maintain a set of half-open intervals supporting addRange(l,r), removeRange(l,r), and queryRange(l,r) (true iff the whole [l,r) is currently tracked).

Examples#

addRange(10,20); removeRange(14,16); queryRange(10,14) → true.
queryRange(13,15) → false; queryRange(16,17) → true.

Constraints#

1 <= l < r <= 10^9, up to 10^4 ops.

Approach#

Store intervals in std::map<int,int> keyed by start, value = end. On add, find overlaps via lower_bound, merge them. On remove, split any straddling interval. On query, find the first interval starting <= l and check that its end >= r.

Solution#

class RangeModule {
    map<int,int> mp; // start -> end (half-open)
public:
    void addRange(int left, int right) {
        auto it = mp.lower_bound(left);
        if (it != mp.begin()) {
            auto p = prev(it);
            if (p->second >= left) { left = p->first; right = max(right, p->second); it = p; }
        }
        while (it != mp.end() && it->first <= right) {
            right = max(right, it->second);
            it = mp.erase(it);
        }
        mp[left] = right;
    }

    bool queryRange(int left, int right) {
        auto it = mp.upper_bound(left);
        if (it == mp.begin()) return false;
        --it;
        return it->second >= right;
    }

    void removeRange(int left, int right) {
        auto it = mp.lower_bound(left);
        if (it != mp.begin()) {
            auto p = prev(it);
            if (p->second > left) {
                int s = p->first, e = p->second;
                mp[s] = left;
                if (e > right) mp[right] = e;
                it = mp.lower_bound(left);
            }
        }
        while (it != mp.end() && it->first < right) {
            if (it->second <= right) it = mp.erase(it);
            else { int e = it->second; mp.erase(it); mp[right] = e; break; }
        }
    }
};

type RangeModule struct {
    starts []int       // sorted interval starts
    ends   map[int]int // start -> end
}

func Constructor() RangeModule {
    return RangeModule{ends: map[int]int{}}
}

func (r *RangeModule) AddRange(left int, right int) {
    i := sort.SearchInts(r.starts, left)
    if i > 0 {
        ps := r.starts[i-1]
        if r.ends[ps] >= left {
            left = ps
            if r.ends[ps] > right {
                right = r.ends[ps]
            }
            delete(r.ends, ps)
            r.starts = append(r.starts[:i-1], r.starts[i:]...)
            i--
        }
    }
    for i < len(r.starts) && r.starts[i] <= right {
        s := r.starts[i]
        if r.ends[s] > right {
            right = r.ends[s]
        }
        delete(r.ends, s)
        r.starts = append(r.starts[:i], r.starts[i+1:]...)
    }
    r.starts = append(r.starts, 0)
    copy(r.starts[i+1:], r.starts[i:])
    r.starts[i] = left
    r.ends[left] = right
}

func (r *RangeModule) QueryRange(left int, right int) bool {
    i := sort.SearchInts(r.starts, left+1)
    if i == 0 {
        return false
    }
    s := r.starts[i-1]
    return r.ends[s] >= right
}

func (r *RangeModule) RemoveRange(left int, right int) {
    i := sort.SearchInts(r.starts, left)
    if i > 0 {
        ps := r.starts[i-1]
        if r.ends[ps] > left {
            e := r.ends[ps]
            r.ends[ps] = left
            if e > right {
                r.starts = append(r.starts, 0)
                copy(r.starts[i+1:], r.starts[i:])
                r.starts[i] = right
                r.ends[right] = e
            }
        }
    }
    for i < len(r.starts) && r.starts[i] < right {
        s := r.starts[i]
        if r.ends[s] <= right {
            delete(r.ends, s)
            r.starts = append(r.starts[:i], r.starts[i+1:]...)
        } else {
            e := r.ends[s]
            delete(r.ends, s)
            r.starts[i] = right
            r.ends[right] = e
            break
        }
    }
}

from sortedcontainers import SortedDict

class RangeModule:
    def __init__(self) -> None:
        self.mp = SortedDict()  # start -> end (half-open)

    def addRange(self, left: int, right: int) -> None:
        idx = self.mp.bisect_left(left)
        keys = self.mp.keys()
        if idx > 0:
            ps = keys[idx - 1]
            if self.mp[ps] >= left:
                left = ps
                right = max(right, self.mp[ps])
                del self.mp[ps]
                idx -= 1
        while idx < len(self.mp) and keys[idx] <= right:
            s = keys[idx]
            right = max(right, self.mp[s])
            del self.mp[s]
        self.mp[left] = right

    def queryRange(self, left: int, right: int) -> bool:
        idx = self.mp.bisect_right(left)
        if idx == 0:
            return False
        s = self.mp.keys()[idx - 1]
        return self.mp[s] >= right

    def removeRange(self, left: int, right: int) -> None:
        idx = self.mp.bisect_left(left)
        keys = self.mp.keys()
        if idx > 0:
            ps = keys[idx - 1]
            if self.mp[ps] > left:
                e = self.mp[ps]
                self.mp[ps] = left
                if e > right:
                    self.mp[right] = e
        idx = self.mp.bisect_left(left)
        while idx < len(self.mp) and keys[idx] < right:
            s = keys[idx]
            if self.mp[s] <= right:
                del self.mp[s]
            else:
                e = self.mp[s]
                del self.mp[s]
                self.mp[right] = e
                break

class RangeModule {
    constructor() {
        this.starts = []; // sorted interval starts
        this.ends = new Map(); // start -> end
    }

    _bisectLeft(x) {
        let lo = 0, hi = this.starts.length;
        while (lo < hi) {
            const m = (lo + hi) >> 1;
            if (this.starts[m] < x) lo = m + 1;
            else hi = m;
        }
        return lo;
    }

    addRange(left, right) {
        let i = this._bisectLeft(left);
        if (i > 0) {
            const ps = this.starts[i - 1];
            if (this.ends.get(ps) >= left) {
                left = ps;
                right = Math.max(right, this.ends.get(ps));
                this.ends.delete(ps);
                this.starts.splice(i - 1, 1);
                i--;
            }
        }
        while (i < this.starts.length && this.starts[i] <= right) {
            const s = this.starts[i];
            right = Math.max(right, this.ends.get(s));
            this.ends.delete(s);
            this.starts.splice(i, 1);
        }
        this.starts.splice(i, 0, left);
        this.ends.set(left, right);
    }

    queryRange(left, right) {
        let lo = 0, hi = this.starts.length;
        while (lo < hi) {
            const m = (lo + hi) >> 1;
            if (this.starts[m] <= left) lo = m + 1;
            else hi = m;
        }
        if (lo === 0) return false;
        const s = this.starts[lo - 1];
        return this.ends.get(s) >= right;
    }

    removeRange(left, right) {
        let i = this._bisectLeft(left);
        if (i > 0) {
            const ps = this.starts[i - 1];
            if (this.ends.get(ps) > left) {
                const e = this.ends.get(ps);
                this.ends.set(ps, left);
                if (e > right) {
                    this.starts.splice(i, 0, right);
                    this.ends.set(right, e);
                }
            }
        }
        i = this._bisectLeft(left);
        while (i < this.starts.length && this.starts[i] < right) {
            const s = this.starts[i];
            if (this.ends.get(s) <= right) {
                this.ends.delete(s);
                this.starts.splice(i, 1);
            } else {
                const e = this.ends.get(s);
                this.ends.delete(s);
                this.starts[i] = right;
                this.ends.set(right, e);
                break;
            }
        }
    }
}

class RangeModule {
    private TreeMap<Integer, Integer> mp; // start -> end (half-open)

    public RangeModule() {
        mp = new TreeMap<>();
    }

    public void addRange(int left, int right) {
        Map.Entry<Integer, Integer> p = mp.floorEntry(left);
        if (p != null && p.getValue() >= left) {
            left = p.getKey();
            right = Math.max(right, p.getValue());
            mp.remove(p.getKey());
        }
        Map.Entry<Integer, Integer> it = mp.ceilingEntry(left);
        while (it != null && it.getKey() <= right) {
            right = Math.max(right, it.getValue());
            mp.remove(it.getKey());
            it = mp.ceilingEntry(left);
        }
        mp.put(left, right);
    }

    public boolean queryRange(int left, int right) {
        Map.Entry<Integer, Integer> p = mp.floorEntry(left);
        if (p == null) return false;
        return p.getValue() >= right;
    }

    public void removeRange(int left, int right) {
        Map.Entry<Integer, Integer> p = mp.floorEntry(left);
        if (p != null && p.getValue() > left) {
            int s = p.getKey(), e = p.getValue();
            mp.put(s, left);
            if (e > right) mp.put(right, e);
        }
        Map.Entry<Integer, Integer> it = mp.ceilingEntry(left);
        while (it != null && it.getKey() < right) {
            if (it.getValue() <= right) {
                mp.remove(it.getKey());
            } else {
                int e = it.getValue();
                mp.remove(it.getKey());
                mp.put(right, e);
                break;
            }
            it = mp.ceilingEntry(left);
        }
    }
}

class RangeModule {
    private starts: number[]; // sorted interval starts
    private ends: Map<number, number>; // start -> end

    constructor() {
        this.starts = [];
        this.ends = new Map<number, number>();
    }

    private bisectLeft(x: number): number {
        let lo = 0, hi = this.starts.length;
        while (lo < hi) {
            const m = (lo + hi) >> 1;
            if (this.starts[m] < x) lo = m + 1;
            else hi = m;
        }
        return lo;
    }

    addRange(left: number, right: number): void {
        let i = this.bisectLeft(left);
        if (i > 0) {
            const ps = this.starts[i - 1];
            if ((this.ends.get(ps) as number) >= left) {
                left = ps;
                right = Math.max(right, this.ends.get(ps) as number);
                this.ends.delete(ps);
                this.starts.splice(i - 1, 1);
                i--;
            }
        }
        while (i < this.starts.length && this.starts[i] <= right) {
            const s = this.starts[i];
            right = Math.max(right, this.ends.get(s) as number);
            this.ends.delete(s);
            this.starts.splice(i, 1);
        }
        this.starts.splice(i, 0, left);
        this.ends.set(left, right);
    }

    queryRange(left: number, right: number): boolean {
        let lo = 0, hi = this.starts.length;
        while (lo < hi) {
            const m = (lo + hi) >> 1;
            if (this.starts[m] <= left) lo = m + 1;
            else hi = m;
        }
        if (lo === 0) return false;
        const s = this.starts[lo - 1];
        return (this.ends.get(s) as number) >= right;
    }

    removeRange(left: number, right: number): void {
        let i = this.bisectLeft(left);
        if (i > 0) {
            const ps = this.starts[i - 1];
            if ((this.ends.get(ps) as number) > left) {
                const e = this.ends.get(ps) as number;
                this.ends.set(ps, left);
                if (e > right) {
                    this.starts.splice(i, 0, right);
                    this.ends.set(right, e);
                }
            }
        }
        i = this.bisectLeft(left);
        while (i < this.starts.length && this.starts[i] < right) {
            const s = this.starts[i];
            if ((this.ends.get(s) as number) <= right) {
                this.ends.delete(s);
                this.starts.splice(i, 1);
            } else {
                const e = this.ends.get(s) as number;
                this.ends.delete(s);
                this.starts[i] = right;
                this.ends.set(right, e);
                break;
            }
        }
    }
}

Editorial#

Half-open [l, r) lets touching intervals merge cleanly without off-by-one drama. The ordered map’s lower_bound plus a single backward step locates the candidate that might contain left — that’s all you need for both queries and merges.

Complexity#

Time: O(log n + k) amortized; total intervals only shrinks across adds.
Space: O(n).

Concept revision#

Insert Interval