値の追加・削除と中央値取得 (structure/others/dynamic-median.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2026-05-17 20:25:54+09:00
• Include: #include "structure/others/dynamic-median.hpp"

概要

• 値を追加・削除しながら、中央値を求める。
• 下側中央値、上側中央値、両側の算術平均を選べる。
• median() は下側中央値を返す。
• lower_values と upper_values の $2$ つの多重集合で値を分けて持つ。

使い方

• DynamicMedian<T>()
  • 空で構築する。
  • 前提：T はコピー可能で、std::multiset<T> で扱える比較を持つ。
• DynamicMedianMode
  • Lower は昇順で $0$ 始まりの $(N - 1) / 2$ 番目の値を指定する。
  • Upper は昇順で $0$ 始まりの $N / 2$ 番目の値を指定する。
  • Average は Lower と Upper の算術平均を指定する。
  • 備考：要素数が奇数の場合、$3$ 種類は同じ値になる。
• void add(T x)
  • 値 $x$ を $1$ 個追加する。
• bool erase(T x)
  • 値 $x$ を $1$ 個削除する。
  • 返り値：削除できたなら true、存在しなければ false。
  • 備考：同じ値が複数ある場合はいずれか $1$ 個だけを削除する。
• template <class Result = T> Result median(DynamicMedianMode mode = DynamicMedianMode::Lower) const
  • mode で指定した中央値を返す。
  • 前提：要素数が $1$ 以上である。
  • 前提：Average を使う場合、Result へ変換した値の加算と $2$ での除算ができる。
  • 備考：Result が整数型の場合は、中央 $2$ 値の和を $2$ で割る整数除算の値を、和のオーバーフローを避けて返す。
  • 備考：平均を小数で返したい場合は median<long double>(DynamicMedianMode::Average) のように指定する。
• std::multiset<T> lower_values
  • 小さい側の値を持つ。
  • 備考：空でなければ最大値が下側中央値である。
• std::multiset<T> upper_values
  • 大きい側の値を持つ。
  • 備考：lower_values の各値は upper_values の各値以下である。

計算量

• 要素数を $N$ とする。
• add, erase: $O(\log N)$
• median: $O(1)$
• 空間：$O(N)$

Verified with

• verify/standalone-dynamic-median.test.cpp
• verify/yukicoder-275.test.cpp

Code

#ifndef STRUCTURE_OTHERS_DYNAMIC_MEDIAN_HPP
#define STRUCTURE_OTHERS_DYNAMIC_MEDIAN_HPP

// 値の多重集合に対して追加、削除、中央値取得を行う。
// 中央値は下側、上側、両側の算術平均から選べる。
// T はコピー可能で、std::multiset で扱える比較を持つ型を仮定する。
// median は空でないことを仮定する。
// add, erase は O(log N)、median は O(1) である。

#include <cassert>
#include <set>
#include <type_traits>

enum class DynamicMedianMode { Lower, Upper, Average };

template <class T> struct DynamicMedian {
    std::multiset<T> lower_values;
    std::multiset<T> upper_values;

    void add(T x) {
        if (lower_values.empty() || !(*lower_values.rbegin() < x)) {
            lower_values.insert(x);
        } else {
            upper_values.insert(x);
        }
        balance();
    }

    bool erase(T x) {
        auto lower_itr = lower_values.find(x);
        if (lower_itr != lower_values.end()) {
            lower_values.erase(lower_itr);
            balance();
            return true;
        }

        auto upper_itr = upper_values.find(x);
        if (upper_itr != upper_values.end()) {
            upper_values.erase(upper_itr);
            balance();
            return true;
        }

        return false;
    }

    template <class Result = T>
    Result median(DynamicMedianMode mode = DynamicMedianMode::Lower) const {
        assert(!lower_values.empty());
        const T &lower_median = *lower_values.rbegin();

        if (mode == DynamicMedianMode::Lower) {
            return static_cast<Result>(lower_median);
        }
        if (lower_values.size() != upper_values.size()) {
            return static_cast<Result>(lower_median);
        }

        const T &upper_median = *upper_values.begin();
        if (mode == DynamicMedianMode::Upper) {
            return static_cast<Result>(upper_median);
        }

        assert(mode == DynamicMedianMode::Average);
        const Result lower = static_cast<Result>(lower_median);
        const Result upper = static_cast<Result>(upper_median);
        if constexpr (std::is_integral_v<Result>) {
            if constexpr (std::is_signed_v<Result>) {
                if (lower < 0 && 0 < upper) {
                    return (lower + upper) / 2;
                }
            }
            return lower / 2 + upper / 2 + (lower % 2 + upper % 2) / 2;
        } else if constexpr (requires(Result lhs, Result rhs) {
                                 (lhs + rhs) / Result(2);
                             }) {
            return (lower + upper) / Result(2);
        } else {
            assert(false);
            return static_cast<Result>(lower_median);
        }
    }

  private:
    void balance() {
        while (lower_values.size() < upper_values.size()) {
            lower_values.insert(*upper_values.begin());
            upper_values.erase(upper_values.begin());
        }
        while (lower_values.size() > upper_values.size() + 1) {
            auto itr = lower_values.end();
            --itr;
            upper_values.insert(*itr);
            lower_values.erase(itr);
        }
    }
};

#endif

#line 1 "structure/others/dynamic-median.hpp"



// 値の多重集合に対して追加、削除、中央値取得を行う。
// 中央値は下側、上側、両側の算術平均から選べる。
// T はコピー可能で、std::multiset で扱える比較を持つ型を仮定する。
// median は空でないことを仮定する。
// add, erase は O(log N)、median は O(1) である。

#include <cassert>
#include <set>
#include <type_traits>

enum class DynamicMedianMode { Lower, Upper, Average };

template <class T> struct DynamicMedian {
    std::multiset<T> lower_values;
    std::multiset<T> upper_values;

    void add(T x) {
        if (lower_values.empty() || !(*lower_values.rbegin() < x)) {
            lower_values.insert(x);
        } else {
            upper_values.insert(x);
        }
        balance();
    }

    bool erase(T x) {
        auto lower_itr = lower_values.find(x);
        if (lower_itr != lower_values.end()) {
            lower_values.erase(lower_itr);
            balance();
            return true;
        }

        auto upper_itr = upper_values.find(x);
        if (upper_itr != upper_values.end()) {
            upper_values.erase(upper_itr);
            balance();
            return true;
        }

        return false;
    }

    template <class Result = T>
    Result median(DynamicMedianMode mode = DynamicMedianMode::Lower) const {
        assert(!lower_values.empty());
        const T &lower_median = *lower_values.rbegin();

        if (mode == DynamicMedianMode::Lower) {
            return static_cast<Result>(lower_median);
        }
        if (lower_values.size() != upper_values.size()) {
            return static_cast<Result>(lower_median);
        }

        const T &upper_median = *upper_values.begin();
        if (mode == DynamicMedianMode::Upper) {
            return static_cast<Result>(upper_median);
        }

        assert(mode == DynamicMedianMode::Average);
        const Result lower = static_cast<Result>(lower_median);
        const Result upper = static_cast<Result>(upper_median);
        if constexpr (std::is_integral_v<Result>) {
            if constexpr (std::is_signed_v<Result>) {
                if (lower < 0 && 0 < upper) {
                    return (lower + upper) / 2;
                }
            }
            return lower / 2 + upper / 2 + (lower % 2 + upper % 2) / 2;
        } else if constexpr (requires(Result lhs, Result rhs) {
                                 (lhs + rhs) / Result(2);
                             }) {
            return (lower + upper) / Result(2);
        } else {
            assert(false);
            return static_cast<Result>(lower_median);
        }
    }

  private:
    void balance() {
        while (lower_values.size() < upper_values.size()) {
            lower_values.insert(*upper_values.begin());
            upper_values.erase(upper_values.begin());
        }
        while (lower_values.size() > upper_values.size() + 1) {
            auto itr = lower_values.end();
            --itr;
            upper_values.insert(*itr);
            lower_values.erase(itr);
        }
    }
};

Back to top page