Kyopro Library
 
読み取り中…
検索中…
一致する文字列を見つけられません
公開メンバ関数 | 静的公開変数類 | 全メンバ一覧
WaveletMatrix 構造体

Wavelet Matrix https://github.com/MitI-7/WaveletMatrix/tree/master/WaveletMatrix https://miti-7.hatenablog.com/entry/2019/02/01/152131 [詳解]

#include "wavelet_matrix.hpp"

公開メンバ関数

 WaveletMatrix (const vector< ull > &a)
 コンストラクタ
 
ull access (ull pos)
 a[pos] を返す
 
ull select (ull c, ull rank)
 rank 番目の c の位置 +1 を返す
 
ull max_range (ull begin_pos, ull end_pos)
 区間 [l, r) で最大のインデックスを返す
 
ull min_range (ull begin_pos, ull end_pos)
 区間 [l, r) で最小のインデックスを返す
 
ull quantile_range (ull begin_pos, ull end_pos, ull k)
 区間 [l, r) で k 番目に小さい値のインデックスを返す
 
ull rank (ull c, ull pos)
 区間 [0, pos) の c の数
 
ull range_freq (ull begin_pos, ull end_pos, ull min_c, ull max_c)
 区間 [l, r) の [min_c, max_c) に入る値の個数
 
ull rank_less_than (ull c, ull begin, ull end)
 区間 [l, r) の c より小さい値の数
 
ull rank_more_than (ull c, ull begin, ull end)
 区間 [l, r) の c より大きい値の数
 
tuple< ull, ull, ull > rank_all (const ull c, ull begin, ull end)
 区間 [l, r) の (c と同じ値の数, c より小さい値の数, c より大きい値の数)
 
vector< pair< ull, ull > > topk (ull begin, ull end, ull k)
 区間 [l, r) で出現回数が多い順に k 個の (値, 頻度) を返す
 
ull range_sum (const ull begin, const ull end, const ull x, const ull y)
 区間 [l, r) で [x, y) に入る値の総和
 
ull prev_value (const ull begin_pos, const ull end_pos, const ull x, ull y)
 
ull next_value (const ull begin_pos, const ull end_pos, const ull x, const ull y)
 
vector< tuple< ull, ull, ull > > intersect (ull _s1, ull _e1, ull _s2, ull _e2)
 

静的公開変数類

static const ull NOTFOUND =SuccinctBitVector::NOTFOUND
 

詳解

Wavelet Matrix https://github.com/MitI-7/WaveletMatrix/tree/master/WaveletMatrix https://miti-7.hatenablog.com/entry/2019/02/01/152131

wavelet_matrix.hpp の 162 行目に定義があります。

構築子と解体子

◆ WaveletMatrix()

WaveletMatrix::WaveletMatrix ( const vector< ull > & a)
inline

コンストラクタ

a から Wavelet Matrix を構築する

wavelet_matrix.hpp の 177 行目に定義があります。

参照先 SuccinctBitVector::SuccinctBitVector().

関数詳解

◆ access()

ull WaveletMatrix::access ( ull pos)
inline

a[pos] を返す

覚え書き
O(log σ)

wavelet_matrix.hpp の 223 行目に定義があります。

参照先 NOTFOUND.

◆ select()

ull WaveletMatrix::select ( ull c,
ull rank )
inline

rank 番目の c の位置 +1 を返す

rank は 1-indexed

覚え書き
O(log σ)

wavelet_matrix.hpp の 238 行目に定義があります。

参照先 NOTFOUND.

◆ max_range()

ull WaveletMatrix::max_range ( ull begin_pos,
ull end_pos )
inline

区間 [l, r) で最大のインデックスを返す

覚え書き
O(log σ)

wavelet_matrix.hpp の 253 行目に定義があります。

参照先 quantile_range().

◆ min_range()

ull WaveletMatrix::min_range ( ull begin_pos,
ull end_pos )
inline

区間 [l, r) で最小のインデックスを返す

覚え書き
O(log σ)

wavelet_matrix.hpp の 259 行目に定義があります。

参照先 quantile_range().

◆ quantile_range()

ull WaveletMatrix::quantile_range ( ull begin_pos,
ull end_pos,
ull k )
inline

区間 [l, r) で k 番目に小さい値のインデックスを返す

k は 0-indexed

覚え書き
O(log σ)

wavelet_matrix.hpp の 266 行目に定義があります。

参照先 NOTFOUND, select().

◆ rank()

ull WaveletMatrix::rank ( ull c,
ull pos )
inline

区間 [0, pos) の c の数

覚え書き
O(log σ)

wavelet_matrix.hpp の 296 行目に定義があります。

◆ range_freq()

ull WaveletMatrix::range_freq ( ull begin_pos,
ull end_pos,
ull min_c,
ull max_c )
inline

区間 [l, r) の [min_c, max_c) に入る値の個数

覚え書き
O(log σ)

wavelet_matrix.hpp の 311 行目に定義があります。

◆ rank_less_than()

ull WaveletMatrix::rank_less_than ( ull c,
ull begin,
ull end )
inline

区間 [l, r) の c より小さい値の数

覚え書き
O(log σ)

wavelet_matrix.hpp の 322 行目に定義があります。

◆ rank_more_than()

ull WaveletMatrix::rank_more_than ( ull c,
ull begin,
ull end )
inline

区間 [l, r) の c より大きい値の数

覚え書き
O(log σ)

wavelet_matrix.hpp の 329 行目に定義があります。

◆ rank_all()

tuple< ull, ull, ull > WaveletMatrix::rank_all ( const ull c,
ull begin,
ull end )
inline

区間 [l, r) の (c と同じ値の数, c より小さい値の数, c より大きい値の数)

覚え書き
O(log σ)

wavelet_matrix.hpp の 336 行目に定義があります。

◆ topk()

vector< pair< ull, ull > > WaveletMatrix::topk ( ull begin,
ull end,
ull k )
inline

区間 [l, r) で出現回数が多い順に k 個の (値, 頻度) を返す

覚え書き
O(log σ)

wavelet_matrix.hpp の 364 行目に定義があります。

◆ range_sum()

ull WaveletMatrix::range_sum ( const ull begin,
const ull end,
const ull x,
const ull y )
inline

区間 [l, r) で [x, y) に入る値の総和

覚え書き
O(log σ)

wavelet_matrix.hpp の 398 行目に定義があります。

◆ prev_value()

ull WaveletMatrix::prev_value ( const ull begin_pos,
const ull end_pos,
const ull x,
ull y )
inline

wavelet_matrix.hpp の 402 行目に定義があります。

参照先 NOTFOUND.

◆ next_value()

ull WaveletMatrix::next_value ( const ull begin_pos,
const ull end_pos,
const ull x,
const ull y )
inline

wavelet_matrix.hpp の 442 行目に定義があります。

参照先 NOTFOUND.

◆ intersect()

vector< tuple< ull, ull, ull > > WaveletMatrix::intersect ( ull _s1,
ull _e1,
ull _s2,
ull _e2 )
inline

wavelet_matrix.hpp の 480 行目に定義があります。

メンバ詳解

◆ NOTFOUND

const ull WaveletMatrix::NOTFOUND =SuccinctBitVector::NOTFOUND
static

wavelet_matrix.hpp の 163 行目に定義があります。

この構造体詳解は次のファイルから抽出されました: