座標圧縮
(library/sequence/compressor.hpp)

• View this file on GitHub
• Last update: 2026-01-20 20:11:22+09:00
• Include: #include "library/sequence/compressor.hpp"

座標圧縮

できること

• 大きさの序列のみを保持したID配列（0-indexed）に圧縮する
• 巨大な値や負の値を含む配列を、要素の種類数（0 ～ size-1）の範囲に収められる
• 圧縮後のIDから元の値を復元できる
• 任意の値が「どのID相当か」を取得できる（二分探索を利用）

計算量

• 構築: $O(NlogN)$
• 圧縮 get_id: $O(logN)$
• 復元 get_val: $O(1)$

使い方

vector<long long> A = {10, 40, 90, 90, 150, 420};

// 1. 構築
Compressor<long long> zip(A);

// 2. 種類数の取得
int sz = zip.size(); // 5

// 3. 値から ID への変換 (二分探索)
int id1 = zip.get_id(90);       // 2 (90 以上の最小 ID)
int id2 = zip.get_upper_id(90); // 3 (90 より大きい最小 ID)

// 4. ID から元の値への復元
long long val = zip.get_val(2); // 90

// 5. 元の配列をすべて圧縮変換する場合
vector<int> z = zip.get_all();

Required by

• Wavelet Search Engine (library/search/binary_search/wavelet_search_engine.hpp)
• 転倒数 (library/sequence/inversion_number.hpp)
• 区間の値の種類数 (library/sequence/static_range_count_distinct.hpp)
• 区間の値の出現回数 (library/sequence/static_range_frequency.hpp)

Verified with

• WaveletSearchEngineのテスト (tests/search.binary_search.wavelet_search_engine.test.cpp)
• 転倒数・座標圧縮・FenwickTreeのテスト (tests/sequence.inversion_number.test.cpp)
• 区間の値の種類数のテスト (tests/sequence.static_range_count_distinct.test.cpp)
• 区間の値の出現回数のテスト (tests/sequence.static_range_frequency.test.cpp)
• Mo's algorithmのテスト (tests/various.mo.test.cpp)

Code

#pragma once
template <typename T> struct Compressor {
    vector<T> origin, dict;
    Compressor(const vector<T> &v) : origin(v), dict(v) {
        sort(dict.begin(), dict.end());
        dict.erase(unique(dict.begin(), dict.end()), dict.end());
    }
    int size() const { return dict.size(); }
    // 値 -> ID (圧縮)
    int get_id(T x) const {
        return lower_bound(dict.begin(), dict.end(), x) - dict.begin();
    }
    // 値 -> ID (upper_bound版)
    int get_upper_id(T x) const {
        return upper_bound(dict.begin(), dict.end(), x) - dict.begin();
    }
    // ID -> 値 (復元)
    T get_val(int id) const { return dict[id]; }
    // すべて圧縮
    vector<int> get_all() {
        vector<int> res;
        for (auto &&x : origin) res.emplace_back(get_id(x));
        return res;
    }
};

#line 2 "library/sequence/compressor.hpp"
template <typename T> struct Compressor {
    vector<T> origin, dict;
    Compressor(const vector<T> &v) : origin(v), dict(v) {
        sort(dict.begin(), dict.end());
        dict.erase(unique(dict.begin(), dict.end()), dict.end());
    }
    int size() const { return dict.size(); }
    // 値 -> ID (圧縮)
    int get_id(T x) const {
        return lower_bound(dict.begin(), dict.end(), x) - dict.begin();
    }
    // 値 -> ID (upper_bound版)
    int get_upper_id(T x) const {
        return upper_bound(dict.begin(), dict.end(), x) - dict.begin();
    }
    // ID -> 値 (復元)
    T get_val(int id) const { return dict[id]; }
    // すべて圧縮
    vector<int> get_all() {
        vector<int> res;
        for (auto &&x : origin) res.emplace_back(get_id(x));
        return res;
    }
};

Back to top page