区間集合
(data-structure/interval-set.hpp)

• View this file on GitHub
• Last update: 2026-06-30 02:52:10+09:00
• Include: #include "data-structure/interval-set.hpp"

半開区間 $[l,r)$ の集合を，互いに交わらず隣接もしない区間列として管理するデータ構造．

add で追加した区間は既存の区間とマージされ，remove で削除した区間は必要に応じて分割される．

• contains(x)：$x$ が集合に含まれるか判定する．
• contains(l, r)：$[l,r)$ がすべて集合に含まれるか判定する．空区間は真．
• get(x)：$x$ を含む管理区間を optional<pair<T, T>> で返す．存在しない場合は nullopt．
• add(x)：$x$ を追加する．内部では $[x,x+1)$ を追加する．
• add(l, r)：$[l,r)$ を追加する．
• remove(x)：$x$ を削除する．内部では $[x,x+1)$ を削除する．
• remove(l, r)：$[l,r)$ を削除する．
• enumerate(l, r)：$[l,r)$ と交わる部分を，交差区間の列として返す．
• mex(x = 0)：$x$ 以上で集合に含まれない最小の値を返す．
• empty()：管理している区間がないか判定する．
• clear()：すべての区間を削除する．
• begin(), end()：管理している区間列を走査する iterator を返す．

単点操作 add(x), remove(x) は $x+1$ を使うため，x < numeric_limits<T>::max() を要求する．

各操作の計算量は，削除またはマージされる区間数を $k$ として $O((k+1)\log N)$． contains, get, mex は，mex が連続する区間をまたぐ場合を除いて $O(\log N)$．

Verified with

• verify/data-structure/UNIT_interval_set.test.cpp

Code

#pragma once

template <class T>
struct IntervalSet {
  using value_type = pair<T, T>;
  IntervalSet() = default;
  bool contains(T x) const {
    auto it = LR.upper_bound({x, INF});
    if (it == LR.begin()) return false;
    --it;
    return it->first <= x && x < it->second;
  }
  bool contains(T l, T r) const {
    assert(l <= r);
    if (l == r) return true;
    auto it = LR.upper_bound({l, INF});
    if (it == LR.begin()) return false;
    --it;
    return it->first <= l && r <= it->second;
  }

  optional<value_type> get(T x) const {
    auto it = LR.upper_bound({x, INF});
    if (it == LR.begin()) return nullopt;
    --it;
    if (it->first <= x && x < it->second) return *it;
    return nullopt;
  }

  void add(T x) {
    assert(x < INF);
    add(x, x + 1);
  }
  void add(T l, T r) {
    assert(l <= r);
    if (l == r) return;

    auto it = LR.upper_bound({l, INF});
    if (it != LR.begin()) {
      auto pre = prev(it);
      if (l <= pre->second) {
        l = pre->first;
        r = max(r, pre->second);
        it = LR.erase(pre);
      }
    }
    while (it != LR.end() && it->first <= r) {
      r = max(r, it->second);
      it = LR.erase(it);
    }
    LR.insert({l, r});
  }

  void remove(T x) {
    assert(x < INF);
    remove(x, x + 1);
  }
  void remove(T l, T r) {
    assert(l <= r);
    if (l == r) return;

    auto it = LR.upper_bound({l, INF});
    if (it != LR.begin()) {
      auto pre = prev(it);
      if (l < pre->second) {
        T l1 = pre->first, r1 = pre->second;
        LR.erase(pre);
        if (l1 < l) LR.insert({l1, l});
        if (r < r1) {
          LR.insert({r, r1});
          return;
        }
      }
    }
    while (it != LR.end() && it->first < r) {
      T r1 = it->second;
      it = LR.erase(it);
      if (r < r1) {
        LR.insert({r, r1});
        break;
      }
    }
  }

  vector<value_type> enumerate(T l, T r) const {
    assert(l <= r);
    vector<value_type> ret;
    if (l == r) return ret;

    auto it = LR.upper_bound({l, INF});
    if (it != LR.begin()) {
      auto pre = prev(it);
      if (l < pre->second) it = pre;
    }
    while (it != LR.end() && it->first < r) {
      ret.push_back({max(l, it->first), min(r, it->second)});
      ++it;
    }
    return ret;
  }

  T mex(T x = 0) const {
    auto it = LR.upper_bound({x, INF});
    if (it != LR.begin()) {
      auto pre = prev(it);
      if (pre->first <= x && x < pre->second) x = pre->second;
    }
    while (it != LR.end() && it->first <= x) {
      if (x < it->second) x = it->second;
      ++it;
    }
    return x;
  }

  bool empty() const { return LR.empty(); }
  void clear() { LR.clear(); }

  auto begin() const { return LR.begin(); }
  auto end() const { return LR.end(); }

 private:
  static constexpr T INF = numeric_limits<T>::max();
  set<value_type> LR;
};

/**
 * @brief 区間集合
 * @docs docs/data-structure/interval-set.md
 */

#line 2 "data-structure/interval-set.hpp"

template <class T>
struct IntervalSet {
  using value_type = pair<T, T>;
  IntervalSet() = default;
  bool contains(T x) const {
    auto it = LR.upper_bound({x, INF});
    if (it == LR.begin()) return false;
    --it;
    return it->first <= x && x < it->second;
  }
  bool contains(T l, T r) const {
    assert(l <= r);
    if (l == r) return true;
    auto it = LR.upper_bound({l, INF});
    if (it == LR.begin()) return false;
    --it;
    return it->first <= l && r <= it->second;
  }

  optional<value_type> get(T x) const {
    auto it = LR.upper_bound({x, INF});
    if (it == LR.begin()) return nullopt;
    --it;
    if (it->first <= x && x < it->second) return *it;
    return nullopt;
  }

  void add(T x) {
    assert(x < INF);
    add(x, x + 1);
  }
  void add(T l, T r) {
    assert(l <= r);
    if (l == r) return;

    auto it = LR.upper_bound({l, INF});
    if (it != LR.begin()) {
      auto pre = prev(it);
      if (l <= pre->second) {
        l = pre->first;
        r = max(r, pre->second);
        it = LR.erase(pre);
      }
    }
    while (it != LR.end() && it->first <= r) {
      r = max(r, it->second);
      it = LR.erase(it);
    }
    LR.insert({l, r});
  }

  void remove(T x) {
    assert(x < INF);
    remove(x, x + 1);
  }
  void remove(T l, T r) {
    assert(l <= r);
    if (l == r) return;

    auto it = LR.upper_bound({l, INF});
    if (it != LR.begin()) {
      auto pre = prev(it);
      if (l < pre->second) {
        T l1 = pre->first, r1 = pre->second;
        LR.erase(pre);
        if (l1 < l) LR.insert({l1, l});
        if (r < r1) {
          LR.insert({r, r1});
          return;
        }
      }
    }
    while (it != LR.end() && it->first < r) {
      T r1 = it->second;
      it = LR.erase(it);
      if (r < r1) {
        LR.insert({r, r1});
        break;
      }
    }
  }

  vector<value_type> enumerate(T l, T r) const {
    assert(l <= r);
    vector<value_type> ret;
    if (l == r) return ret;

    auto it = LR.upper_bound({l, INF});
    if (it != LR.begin()) {
      auto pre = prev(it);
      if (l < pre->second) it = pre;
    }
    while (it != LR.end() && it->first < r) {
      ret.push_back({max(l, it->first), min(r, it->second)});
      ++it;
    }
    return ret;
  }

  T mex(T x = 0) const {
    auto it = LR.upper_bound({x, INF});
    if (it != LR.begin()) {
      auto pre = prev(it);
      if (pre->first <= x && x < pre->second) x = pre->second;
    }
    while (it != LR.end() && it->first <= x) {
      if (x < it->second) x = it->second;
      ++it;
    }
    return x;
  }

  bool empty() const { return LR.empty(); }
  void clear() { LR.clear(); }

  auto begin() const { return LR.begin(); }
  auto end() const { return LR.end(); }

 private:
  static constexpr T INF = numeric_limits<T>::max();
  set<value_type> LR;
};

/**
 * @brief 区間集合
 * @docs docs/data-structure/interval-set.md
 */

Back to top page