WaveletMatrixRectangleSum

クラス · キー区間に含まれる重みの総和も扱うウェーブレット行列

template <class T, class U = T, int L = 30>
struct WaveletMatrixRectangleSum : private internal::WaveletMatrixCore<internal::bit_vector, T, L>;

概要

キー区間に含まれる重みの総和も扱うウェーブレット行列

計算量

構築は $O(nL)$、total_sum は $O(1)$、他の問い合わせは $O(L)$

構築・破棄

名前	説明	計算量
`(constructor)`	(1) 空の重み付きウェーブレット行列を作る (2) キー列 `v` と対応する重み列 `u` から構築する	(1) $O(1)$ (2) $O(nL)$

メンバ関数

名前	説明	計算量
`total_sum`	区間 $[l,r)$ の重みの総和を返す	$O(1)$
`kth_smallest_sum`	区間 $[l,r)$ のキーが小さい方から `k` 個の重みの総和を返す	$O(L)$
`kth_largest_sum`	区間 $[l,r)$ のキーが大きい方から `k` 個の重みの総和を返す	$O(L)$
`range_sum`	(1) 区間 $[0,r)$ でキーが `x` と等しい要素の重みの総和を返す (2) 区間 $[l,r)$ でキーが `x` と等しい要素の重みの総和を返す	$O(L)$
`rect_sum`	(1) 区間 $[l,r)$ でキーが `upper` 未満の要素の重みの総和を返す (2) 区間 $[l,r)$ でキーが $[lower,upper)$ 内の要素の重みの総和を返す	$O(L)$
`rect_count_sum`	区間 $[l,r)$ でキーが `upper` 未満の要素数と重みの総和を返す	$O(L)$

メンバ型

名前	説明	計算量
`Base`	共通実装の基底型	型エイリアスのため実行時コストなし
`length`	要素数を保持する基底クラスのメンバ	$O(1)$ で参照可能
`matrix`	各レベルのビットベクトルを保持する基底クラスのメンバ	1 レベルの参照は $O(1)$
`mid`	各レベルの 0 の個数を保持する基底クラスのメンバ	1 レベルの参照は $O(1)$
`succ`	あるビットを選んだ後の区間へ写す基底クラスの補助関数	$O(1)$

メンバの詳細

(constructor)

// (1)
WaveletMatrixRectangleSum() = default;

// (2)
template <class Value>
WaveletMatrixRectangleSum(const std::vector<T> &v, const std::vector<Value> &u);

(1) 空の重み付きウェーブレット行列を作る

計算量: $O(1)$

(2) キー列 v と対応する重み列 u から構築する

計算量: $O(nL)$

kth_smallest_sum

U kth_smallest_sum(int l, int r, int k) const;

区間 $[l,r)$ のキーが小さい方から k 個の重みの総和を返す

U == T かつ u == v なら、k 個の最小値の総和になる。

計算量: $O(L)$

kth_largest_sum

U kth_largest_sum(int l, int r, int k) const;

区間 $[l,r)$ のキーが大きい方から k 個の重みの総和を返す

U == T かつ u == v なら、k 個の最大値の総和になる。

計算量: $O(L)$

range_sum

// (1)
U range_sum(int r, T x) const;

// (2)
U range_sum(int l, int r, T x) const;

(1) 区間 $[0,r)$ でキーが x と等しい要素の重みの総和を返す

計算量: $O(L)$

(2) 区間 $[l,r)$ でキーが x と等しい要素の重みの総和を返す

計算量: $O(L)$

rect_sum

// (1)
U rect_sum(int l, int r, T upper) const;

// (2)
U rect_sum(int l, int r, T lower, T upper) const;

(1) 区間 $[l,r)$ でキーが upper 未満の要素の重みの総和を返す

計算量: $O(L)$

(2) 区間 $[l,r)$ でキーが $[lower,upper)$ 内の要素の重みの総和を返す

計算量: $O(L)$