priority_k_sum

クラス · 多重集合の小さい方または大きい方からk個の総和を管理する

template <typename T, class Comp, class RComp>
struct priority_k_sum;

概要

多重集合の小さい方または大きい方からk個の総和を管理する

minimum_sum<T> は最小k個、maximum_sum<T> は最大k個を管理する。

計算量

insert・erase は $O(\log n)$、query・sum は $O(1)$。 set_k は $O((1+|\Delta k|)\log n)$

構築・破棄

名前	説明	計算量
`(constructor)`	集約対象の要素数を `k` として空の多重集合を作る	$O(1)$

メンバ関数

名前	説明	計算量
`size`	多重集合の全要素数を返す	$O(1)$
`query`	比較順で先頭の `k` 個の総和を返す	$O(1)$
`sum`	`query()` の別名	$O(1)$
`get_k`	現在の `k` を返す	$O(1)$
`set_k`	集約対象の要素数を `x` に変更する	$O((1+\|x-k\|)\log n)$
`insert`	(1) 要素 `x` を追加する (2) 要素 `x` をムーブして追加する	$O(\log n)$
`erase`	要素 `x` を 1 個削除する	$O(\log n)$
`last_in`	集約対象側の境界要素を返す	$O(1)$
`last_out`	集約対象外側の境界要素を返す	$O(1)$

メンバの詳細

insert

// (1)
void insert(const T &x);

// (2)
void insert(T &&x);

(1) 要素 x を追加する

計算量: $O(\log n)$

(2) 要素 x をムーブして追加する

計算量: $O(\log n)$

erase

// (1)
void erase(const T &x);

// (2)
void erase(T &&x);

(1)、(2) 要素 x を 1 個削除する

計算量: $O(\log n)$

関連項目

maximum_sum — 多重集合の最大 k 要素の総和を管理する型
minimum_sum — 多重集合の最小 k 要素の総和を管理する型