C++ 범위 모듈(Range Module) 구현: 구간 추가·조회·삭제를 효율적으로 처리하는 방법

숫자들의 구간(범위)을 추적하는 범위 모듈(Range Module)이 필요하다고 가정해 보겠습니다. 이 모듈은 특정 실수 구간이 현재 추적 중인지 확인하고, 구간을 동적으로 추가하거나 제거할 수 있어야 합니다. 우리의 과제는 다음 인터페이스를 효율적으로 설계하고 구현하는 것입니다.

구현해야 할 인터페이스

addRange(left, right) — 반개구간 [left, right)에 포함된 모든 실수를 추적 대상에 추가합니다. 이미 추적 중인 구간과 부분적으로 겹치더라도, 아직 추적되지 않은 숫자만 새로 추가됩니다.
queryRange(left, right) — 구간 [left, right)에 속한 모든 실수가 현재 추적 중이라면 true를 반환합니다.
removeRange(left, right) — 구간 [left, right)에서 현재 추적 중인 모든 실수의 추적을 중단합니다.

해결 접근 방식

이 문제는 정렬된 맵(std::map<int, int>) 하나로 '구간 시작점 → 끝점' 정보를 관리하면 효율적으로 해결할 수 있습니다. 각 연산은 다음 단계로 처리합니다.

1. addRange(left, right)

먼저 removeRange(left, right)를 호출해 새 구간과 겹치는 기존 구간을 제거합니다.
m[left] = right로 새 구간을 삽입한 뒤, left에 해당하는 반복자를 찾습니다.
반복자가 맵의 첫 요소가 아니고, 바로 앞 구간의 끝점이 left와 같다면 두 구간을 병합합니다. 반복자를 하나 감소시키고, 그 구간의 끝점을 right로 갱신한 후 맵에서 left를 삭제합니다.
반복자가 마지막 요소의 앞이 아니고, 바로 뒤 구간의 시작점이 right와 같다면 역시 병합합니다. 현재 구간의 끝점을 다음 구간의 끝점으로 바꾸고 다음 항목을 삭제합니다.

2. queryRange(left, right)

m.upper_bound(left)로 left보다 큰 키 중 첫 번째 위치를 찾습니다.
맵이 비어 있거나 해당 위치가 맵의 시작이라면 false를 반환합니다.
반복자를 하나 감소시킨 뒤, 그 구간의 끝점이 right 이상이면 true를 반환합니다.

3. removeRange(left, right)

맵이 비어 있으면 즉시 반환합니다.
m.lower_bound(left)를 찾고, 시작 위치가 아니라면 반복자를 하나 감소시킵니다.
삭제할 키를 임시로 담을 배열 v를 준비합니다.
반복자가 끝이 아니고 현재 구간의 시작점이 right보다 작은 동안 다음을 반복합니다.
- 구간이 left를 걸쳐 있는 경우(first < left && second > left): 끝점을 left로 줄여 왼쪽 일부만 남기고, 원래 끝점이 right보다 크면 m[right]에 오른쪽 나머지 부분을 저장합니다.
- 구간의 시작점이 left 이상인 경우: 해당 키를 v에 기록하고, 끝점이 right보다 크면 m[right]에 오른쪽 나머지 부분을 저장합니다.
반복이 끝나면 v에 기록된 모든 키를 맵에서 삭제하여 제거된 구간을 정리합니다.

C++ 구현 예제

아래 코드를 통해 더 잘 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class RangeModule {
public:
    map <int, int> m;
    RangeModule() {
    }
    void addRange(int left, int right) {
        removeRange(left, right);
        m[left] = right;
        map <int, int> :: iterator it = m.find(left);
        if(it != m.begin() && prev(it)->second == left){
            it--;
            it->second = right;
            m.erase(left);
        }
        if(it != prev(m.end()) && next(it)->first == right){
            it->second = next(it)->second;
            m.erase(next(it));
        }
    }
    bool queryRange(int left, int right) {
        map <int, int> :: iterator it = m.upper_bound(left);
        if(m.empty() || it == m.begin())return false;
        it--;
        return it->second >= right;
    }
    void removeRange(int left, int right) {
        if(m.empty())return;
        map <int, int> :: iterator it = m.lower_bound(left);
        if(it != m.begin())it--;
        vector <int> v;
        while(it != m.end() && it->first < right){
            if(it->first < left && it->second > left){
                int temp = it->second;
                it->second = left;
                if(temp > right){
                    m[right] = temp;
                }
            }else if(it->first >= left){
                v.push_back(it->first);
                if(it->second > right){
                    m[right] = it->second;
                }
            }
            it++;
        }
        for(int i = 0; i < v.size(); i++){
            m.erase(v[i]);
        }
    }
};
main(){
    RangeModule ob;
    ob.addRange(10,20);
    ob.removeRange(14,16);
    cout << (ob.queryRange(10,14)) << endl;
    cout << (ob.queryRange(13,15)) << endl;
    cout << (ob.queryRange(16,17));
}

입력

Add range (10,20)
Remove Range (14,16)
Check ranges (10,14), (13,15), (16,17)

출력

1
0
1

결과 해석

먼저 구간 (10, 20)을 추가한 뒤, 그중 (14, 16)을 제거했습니다. 이 상태에서 각 쿼리 결과는 다음과 같습니다.

queryRange(10, 14) → 1(true): 10~14 구간은 여전히 온전히 추적 중입니다.
queryRange(13, 15) → 0(false): 14~16이 제거되었기 때문에 13~15 전체가 추적되지 않습니다.
queryRange(16, 17) → 1(true): 16~17 구간 역시 여전히 추적 중입니다.

이처럼 std::map의 정렬된 특성과 upper_bound, lower_bound를 활용하면 구간 병합·분할·조회를 각 연산당 O(log n) 수준의 탐색 비용으로 처리할 수 있어, 범위 모듈을 매우 효율적으로 구현할 수 있습니다.