class NgLib::PrioritySum(T)

Overview

昇順（降順） $k$ 個の総和を効率良く求めるためのデータ構造です。

値の追加、削除、$k$ の変更ができます。

Defined in:

nglib/data_structure/priority_sum.cr

Constructors

Class Method Summary

Instance Method Summary

Constructor Detail

def self.new(tag : Symbol, k : Int, initial : T = T.zero) #

[View source]

Class Method Detail

def self.max(k : Int, initial : T = T.zero) #

上位 $k$ 要素の総和を求めるためのデータ構造を構築します。


[View source]
def self.min(k : Int, initial : T = T.zero) #

下位 $k$ 要素の総和を求めるためのデータ構造を構築します。


[View source]

Instance Method Detail

def <<(x : T) #

Alias for #add


[View source]
def add(x : T) #

要素 $x$ をデータ構造に追加します。

計算量は $O(\log{n})$ です。


[View source]
def delete(x : T) #

要素 $x$ をデータ構造から削除します。

計算量は $O(\log{n})$ です。


[View source]
def empty?(*args, **options) #

[View source]
def empty?(*args, **options, &) #

[View source]
def k : Int32 #

[View source]
def k=(k : Int) #

$k$ の値を変更します。

計算量は $\Delta k \log{\Delta k}$


[View source]
def size(*args, **options) #

[View source]
def size(*args, **options, &) #

[View source]
def sum : T #

[View source]