「区間をsetで管理するやつ」を「IntervalSet」と呼びませんか

言いたいこと

　いわゆる「区間をsetで管理するやつ」と呼ばれるデータ構造について、より扱いやすい名称として 「IntervalSet」 という名称を使うことを提案します。

　ちなみに、ライブラリは けんちょん氏による IntervalSet がおすすめです。

この名称に決めた理由

• 現在最も汎用性が高いであろう、けんちょん氏によるライブラリがこの名称を使用している
• 区間（Interval）を set を使って管理するという実態と一致している
• 「IntervalSet」で検索しても、そこまで他の用語と衝突しやすくないため、識別性も低くない

　といったことから、この名称をより一般的な（けんちょん氏のライブラリに限らず、同じアイデアを使ったデータ構造を指す）名称として使用した方がよいと考えました。

　なお、この記事を書いた一番大きな理由は、「区間をsetで管理するやつ」で検索すると、あまり本筋でない 私の記事 がトップヒットしてしまうため、経緯をまとめて正しい方向に誘導する責任を感じた ためです。

「区間をsetで管理するやつ」を巡る経緯

• 2020年10月。えびちゃん さんが 要素の追加・削除と mex を対数時間で処理するよ を公開。根本的なアイデアが文章化された初めての機会？
• その後、複数のブログにおいて「区間を set で管理するやつ」という名称が使われ、事実上この名称で固定されていく
• 2022年6月。Nyaan さんによる ABC公式解説 で、「区間を set で管理するテクニック」という言及がされる。
• 2023年11月。nok0 さんによる ABCユーザー解説 で、「『区間を set で管理するテクニック』と俗に呼ばれている手法を用いることで簡単に解くことができます。」という言及がなされる。俗称はあるが正式名称は決まっていない、という状況であることが再確認される。
• 2025年4月。けんちょん さんが IntervalSet を公開。

　ということで、この種のデータ構造については、「区間をsetで管理するやつ」という「一般名称らしからぬ名称」が事実上の一般名称として使われている、という状態が続いていました。望ましくない、というのは言い過ぎですが、是正できるのならばした方が良い状況だと思います。

　そのような中、けんちょん氏が IntervalSet という名前でライブラリを公開したので、それを一般名称として統一させた方が良いと考えました。もちろん、それ以外の人が、同じ根本的着想をもとに別のライブラリを持っても、それは別の IntervalSet と呼ばれるべきだと思います。

けんちょん氏の IntervalSet で何かできるか

　ライブラリ のページに活用例のコードがそのまま載っているので、それを参考にするのが良いと思われます。

　ほかの活用例を以下に載せます。

座標圧縮

　個数と値のペアを持つことによって事実上の座標圧縮ができます。

具体的な実装

int main(){
    IntervalSet<ll> st;
    int q;
    cin >> q;
    ll idx = 0;
    ll tail = 0;
    while(q--){
        int t;
        cin >> t;
        if(t==1){
            ll c,x;
            cin >> c >> x;
            st.update(tail,tail+c,x);
            tail += c;
        }
        if(t==2){
            ll k;
            cin >> k;
            // debug(k);
            ll ans = 0;
            auto add = [&](ll L,ll R,ll val)->void {
                ans -= (R-L)*val;
                return;
            };
            auto del = [&](ll L,ll R,ll val)->void {
                ans += (R-L)*val;
                return;
            };
            st.update(idx,idx+k,0,add,del);
            idx += k;
            cout << ans << endl;
        }
    }
}

同一値の連続区間

具体的な実装

int main(){
    int n,q;
    cin >> n >> q;
    IntervalSet<ll> st;
    vector<int> ans(n+1);
    rep(i,n){
        st.update(i,i+1,i+1);
        ans[i+1]++;
    }
    while(q--){
        int t;
        cin >> t;
        if(t==1){
            int x,c;
            cin >> x >> c;
            x--;
            auto node = *st.get(x);
            auto [L,R,val] = node;
            auto add = [&](int left,int right,int value){
                ans[value] += right-left;
                return;
            };
            auto del = [&](int left,int right,int value){
                ans[value] -= right-left;
                return;
            };
            st.update(L,R,c,add,del);
        }else{
            int c;
            cin >> c;
            cout << ans[c] << endl;
        }
    }
}

　このように、多くの問題を殴れることがわかります。