FilteredSegmentTree
クラス · 要素を特定のキー（条件）でフィルタリングして区間取得を行えるセグメント木
template <class K, monoid M>
struct FilteredSegmentTree;
概要
要素を特定のキー（条件）でフィルタリングして区間取得を行えるセグメント木
テンプレートパラメータ
| 名前 | 説明 |
|---|---|
K |
フィルタリングに用いるキーの型 |
計算量
- 構築 $O(N \log N)$、更新・問合せ $O(\log N)$
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
構築 $O(N \log N)$ | $O(N \log N)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
set |
k 番目の要素を val に更新する |
$O(\log N)$ |
prod |
区間 $[a, b)$ のうち、キーが key である要素の総積を取得する |
$O(\log N)$ |
prod_or_default |
区間 $[a, b)$ のうち、キーが key である要素の総積を取得する。ただし単位元の場合は default_value |
$O(\log N)$ |
メンバの詳細
(constructor)
FilteredSegmentTree(const std::vector<K> &keys, const std::vector<T> &_values);
構築 $O(N \log N)$
- パラメータ
keys: 各要素が属するキー - パラメータ
_values: 各要素の初期値 - 計算量: $O(N \log N)$
set
void set(int k, T val);
k 番目の要素を val に更新する
- パラメータ
k: 更新する要素の元のインデックス - パラメータ
val: 新しい値 - 計算量: $O(\log N)$
prod
T prod(int a, int b, K key) const;
区間 $[a, b)$ のうち、キーが key である要素の総積を取得する
- パラメータ
a: 区間の左端 (含む) - パラメータ
b: 区間の右端 (含まない) - パラメータ
key: 対象とするキー - 戻り値: 対象要素の総積。存在しない場合はモノイドの単位元
- 計算量: $O(\log N)$
prod_or_default
T prod_or_default(int a, int b, K key, T default_value) const;
区間 $[a, b)$ のうち、キーが key である要素の総積を取得する。ただし単位元の場合は default_value
を返す
- パラメータ
a: 区間の左端 (含む) - パラメータ
b: 区間の右端 (含まない) - パラメータ
key: 対象とするキー - パラメータ
default_value: 要素が存在しない/単位元の場合のデフォルト値 - 戻り値: 対象要素の総積、または
default_value - 計算量: $O(\log N)$