区間の値の出現回数
(library/sequence/static_range_frequency.hpp)

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

区間の値の出現回数

できること

• 静的な配列に対して、指定された範囲 $[l, r)$ 内の値が出現する回数を求める
• 先にクエリをすべて読むオフラインクエリ
• 座標圧縮と二分探索で実現

計算量

$O(N \log N)$

使い方

// 1. 数値配列の例
vector<int> a = {1, 2, 1, 3, 1, 4, 1};
StaticRangeFrequency srf(a);

// インデックス 0から4 ([0, 4)) の範囲にある '1' の個数
// a[0], a[1], a[2], a[3] -> {1, 2, 1, 3} なので 2個
cout << "Count of 1 in a[0, 4): " << srf.query(0, 4, 1) << endl;

// インデックス 0から7 ([0, 7)) の全範囲にある '1' の個数 -> 4個
cout << "Count of 1 in a[0, 7): " << srf.query(0, 7, 1) << endl;

// 存在しない値を投げても 0 が返る
cout << "Count of 100 in a[0, 7): " << srf.query(0, 7, 100) << endl;

// ---
// 2. 文字列配列の例
vector<string> b = {"apple", "orange", "apple", "banana"};
StaticRangeFrequency srf_str(b);

// [0, 3) の範囲にある "apple" の個数 -> 2個
cout << "Count of 'apple' in b[0, 3): " << srf_str.query(0, 3, "apple") << endl;

Depends on

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

Verified with

• 区間の値の出現回数のテスト (tests/sequence.static_range_frequency.test.cpp)

Code

#pragma once
#include "library/sequence/compressor.hpp"
template <typename T> struct StaticRangeFrequency {
  private:
    Compressor<T> comp;
    vector<vector<int>> mp;

  public:
    explicit StaticRangeFrequency(const vector<T> &xs) : comp(xs) {
        mp.resize(comp.size());
        for (int i = 0; i < (int)xs.size(); ++i) {
            int id = comp.get_id(xs[i]);
            mp[id].emplace_back(i);
        }
    }
    int query(int l, int r, T x) const {
        int id = comp.get_id(x);
        if (id >= (int)comp.size() or comp.get_val(id) != x) return 0ll;
        const auto &pos = mp[id];
        return lower_bound(pos.begin(), pos.end(), r) -
               lower_bound(pos.begin(), pos.end(), l);
    }
};

#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;
    }
};
#line 3 "library/sequence/static_range_frequency.hpp"
template <typename T> struct StaticRangeFrequency {
  private:
    Compressor<T> comp;
    vector<vector<int>> mp;

  public:
    explicit StaticRangeFrequency(const vector<T> &xs) : comp(xs) {
        mp.resize(comp.size());
        for (int i = 0; i < (int)xs.size(); ++i) {
            int id = comp.get_id(xs[i]);
            mp[id].emplace_back(i);
        }
    }
    int query(int l, int r, T x) const {
        int id = comp.get_id(x);
        if (id >= (int)comp.size() or comp.get_val(id) != x) return 0ll;
        const auto &pos = mp[id];
        return lower_bound(pos.begin(), pos.end(), r) -
               lower_bound(pos.begin(), pos.end(), l);
    }
};

Back to top page