区間の k 番目に小さい値を求めるクエリ
(data_structure/range_kth_smallest.hpp)

• View this file on GitHub
• Last update: 2026-04-12 20:46:15+09:00
• Include: #include "data_structure/range_kth_smallest.hpp"

長さ $n$ の配列 $a$ に対し、区間 $[l, r)$ の $k$ 番目に小さい値を求めます。

コンストラクタ

RangeKthSmallest<T> rks(std::vector<T> a)

長さ $n$ の数列 $a$ で初期化します。

計算量

• $O(n \log n)$

query

T query(int l, int r, int k)

長さ $n$ の配列 $a$ に対し、区間 $[l, r)$ の $k$ 番目に小さい値を求めます。

$k$ は 0-indexed です。

制約

• $0 \leq l < r \leq n$
• $0 \leq k < r - l$

計算量

• $O(\log^2 n)$

参考文献

• 永続セグメント木 - AtCoderInfo

Depends on

• algebra/monoid/monoid_plus.hpp
• Persistent Segment Tree (永続セグメント木) (segment_tree/persistent_segment_tree.hpp)

Verified with

• data_structure/test/range_kth_smallest.test.cpp

Code

#pragma once

#include <algorithm>

#include "../algebra/monoid/monoid_plus.hpp"
#include "../segment_tree/persistent_segment_tree.hpp"

template <class T> struct RangeKthSmallest {
  public:
    RangeKthSmallest() = default;

    explicit RangeKthSmallest(const std::vector<T>& a)
        : n((int)(a.size())), comp(a) {
        std::sort(comp.begin(), comp.end());
        comp.erase(std::unique(comp.begin(), comp.end()), comp.end());
        m = (int)(comp.size());
        seg = PersistentSegmentTree<MonoidPlus<int>>(m);
        for (int i = 0; i < n; i++) {
            int index =
                std::lower_bound(comp.begin(), comp.end(), a[i]) - comp.begin();
            seg.add(index, 1);
        }
    }

    T query(int l, int r, int k) {
        assert(0 <= l and l < r and r <= n);
        assert(0 <= k and k < r - l);
        auto f = [&](int v) -> bool {
            return seg.prod(0, v, r) - seg.prod(0, v, l) >= k + 1;
        };
        int ok = m, ng = 0;
        while (ok - ng > 1) {
            int md = (ok + ng) / 2;
            if (f(md)) {
                ok = md;
            } else {
                ng = md;
            }
        }
        return comp[ok - 1];
    }

  private:
    int n, m;
    std::vector<T> comp;
    PersistentSegmentTree<MonoidPlus<int>> seg;
};

#line 2 "data_structure/range_kth_smallest.hpp"

#include <algorithm>

#line 2 "algebra/monoid/monoid_plus.hpp"

template <class T> struct MonoidPlus {
    using value_type = T;
    static constexpr T operation(const T& a, const T& b) noexcept {
        return a + b;
    }
    static constexpr T identity() noexcept { return T(0); }
    static constexpr T inverse(const T& a) noexcept { return -a; }
    static constexpr bool commutative = true;
};
#line 2 "segment_tree/persistent_segment_tree.hpp"

#include <cassert>
#include <vector>

// Persistent Segment Tree
// N + Q log_2(N) は N = Q = 500000 のとき 10000000 くらい
template <class MS, int MAX_NODES = 20'000'000> struct PersistentSegmentTree {
  public:
    using S = typename MS::value_type;

    struct Node {
        S d;
        Node *l, *r;
        Node() = default;
        Node(S v, Node* l = nullptr, Node* r = nullptr) : d(v), l(l), r(r) {}
    };

    PersistentSegmentTree() = default;

    explicit PersistentSegmentTree(int n)
        : PersistentSegmentTree(std::vector<S>(n, MS::identity())) {}

    explicit PersistentSegmentTree(const std::vector<S>& v)
        : n((int)(v.size())) {
        roots.push_back(build(v, 0, n));
    }

    int get_time() { return (int)(roots.size()) - 1; }

    Node* set(int p, const S& x, Node* root) {
        assert(0 <= p and p < n);
        roots.push_back(set(p, x, 0, n, root));
        return roots.back();
    }

    Node* set(int p, const S& x) { return set(p, x, roots.back()); }

    Node* set(int p, const S& x, int t) {
        assert(0 <= t and t < (int)(roots.size()));
        return set(p, x, roots[t]);
    }

    Node* add(int p, const S& x, Node* root) {
        assert(0 <= p and p < n);
        roots.push_back(add(p, x, 0, n, root));
        return roots.back();
    }

    Node* add(int p, const S& x) { return add(p, x, roots.back()); }

    Node* add(int p, const S& x, int t) {
        assert(0 <= t and t < (int)(roots.size()));
        return add(p, x, roots[t]);
    }

    S get(int p, Node* root) const {
        assert(0 <= p and p < n);
        return prod(p, p + 1, root);
    }

    S get(int p) const { return get(p, roots.back()); }

    S get(int p, int t) const {
        assert(0 <= t and t < (int)(roots.size()));
        return get(p, roots[t]);
    }

    S operator[](int p) const {
        assert(0 <= p and p < n);
        return prod(p, p + 1);
    }

    S prod(int l, int r, Node* root) const {
        assert(0 <= l and l <= r and r <= n);
        return prod(l, r, 0, n, root);
    }

    S prod(int l, int r) const { return prod(l, r, roots.back()); }

    S prod(int l, int r, int t) const {
        assert(0 <= t and t < (int)(roots.size()));
        return prod(l, r, roots[t]);
    }

    S all_prod(Node* root) const { return root->d; }

    S all_prod() const { return all_prod(roots.back()); }

    S all_prod(int t) const {
        assert(0 <= t and t < (int)(roots.size()));
        return all_prod(roots[t]);
    }

    std::vector<S> make_vector(Node* root) const {
        std::vector<S> vec(n);
        for (int i = 0; i < n; i++) vec[i] = get(i, root);
        return vec;
    }

    std::vector<S> make_vector() const { return make_vector(roots.back()); }

    std::vector<S> make_vector(int t) const {
        assert(0 <= t and t < (int)(roots.size()));
        return make_vector(roots[t]);
    }

  private:
    int n;
    std::vector<Node*> roots;
    static inline Node pool[MAX_NODES];
    static inline int pool_idx = 0;

    Node* new_node(S v, Node* l = nullptr, Node* r = nullptr) {
        return &(pool[pool_idx++] = Node(v, l, r));
    }

    Node* merge(Node* l, Node* r) {
        return new_node(MS::operation(l->d, r->d), l, r);
    }

    Node* build(const std::vector<S>& v, int l, int r) {
        if (l + 1 == r) {
            return new_node(v[l]);
        }
        int m = (l + r) / 2;
        return merge(build(v, l, m), build(v, m, r));
    }

    Node* set(int p, const S& x, int l, int r, Node* np) {
        if (l + 1 == r) {
            return new_node(x);
        }
        int m = (l + r) / 2;
        if (l <= p and p < m) {
            return merge(set(p, x, l, m, np->l), np->r);
        } else {
            return merge(np->l, set(p, x, m, r, np->r));
        }
    }

    Node* add(int p, const S& x, int l, int r, Node* np) {
        if (l + 1 == r) {
            return new_node(MS::operation(np->d, x));
        }
        int m = (l + r) / 2;
        if (l <= p and p < m) {
            return merge(add(p, x, l, m, np->l), np->r);
        } else {
            return merge(np->l, add(p, x, m, r, np->r));
        }
    }

    S prod(int ql, int qr, int l, int r, Node* np) const {
        // [ql, qr) と [l, r) が交差しない
        if (qr <= l or r <= ql) return MS::identity();
        // [ql, qr) が [l, r) を完全に含んでいる
        if (ql <= l and r <= qr) return np->d;
        int m = (l + r) / 2;
        return MS::operation(prod(ql, qr, l, m, np->l),
                             prod(ql, qr, m, r, np->r));
    }
};
#line 7 "data_structure/range_kth_smallest.hpp"

template <class T> struct RangeKthSmallest {
  public:
    RangeKthSmallest() = default;

    explicit RangeKthSmallest(const std::vector<T>& a)
        : n((int)(a.size())), comp(a) {
        std::sort(comp.begin(), comp.end());
        comp.erase(std::unique(comp.begin(), comp.end()), comp.end());
        m = (int)(comp.size());
        seg = PersistentSegmentTree<MonoidPlus<int>>(m);
        for (int i = 0; i < n; i++) {
            int index =
                std::lower_bound(comp.begin(), comp.end(), a[i]) - comp.begin();
            seg.add(index, 1);
        }
    }

    T query(int l, int r, int k) {
        assert(0 <= l and l < r and r <= n);
        assert(0 <= k and k < r - l);
        auto f = [&](int v) -> bool {
            return seg.prod(0, v, r) - seg.prod(0, v, l) >= k + 1;
        };
        int ok = m, ng = 0;
        while (ok - ng > 1) {
            int md = (ok + ng) / 2;
            if (f(md)) {
                ok = md;
            } else {
                ng = md;
            }
        }
        return comp[ok - 1];
    }

  private:
    int n, m;
    std::vector<T> comp;
    PersistentSegmentTree<MonoidPlus<int>> seg;
};

Back to top page