パッケージ library

クラス Tree.IndexedSegmentTree<T>

java.lang.Object

library.Tree.IndexedSegmentTree<T>

型パラメータ:

T -

含まれているクラス:

Tree

private static class Tree.IndexedSegmentTree<T>
extends java.lang.Object

インデックス付きSegment Tree

Segment Treeのクエリ結果に，その結果のインデックスを付与したデータ構造 クエリ結果の値を更新したい場合などに使える

ネストされたクラスの概要

ネストされたクラス

修飾子とタイプ	クラス	説明
private static class	Tree.IndexedSegmentTree.IndexedValue<T>

フィールドの概要

フィールド

修飾子とタイプ	フィールド	説明
private java.util.function.BinaryOperator<Tree.IndexedSegmentTree.IndexedValue<T>>	comparator
private int	exponent
private Tree.IndexedSegmentTree.IndexedValue<T>	initialValue
private Tree.IndexedSegmentTree.IndexedValue<T>[]	internalArray

コンストラクタの概要

コンストラクタ

コンストラクタ	説明
IndexedSegmentTree(int size, T initialValue, java.util.function.BinaryOperator<T> comparator)
IndexedSegmentTree(java.util.List<T> list, T initialValue, java.util.function.BinaryOperator<T> comparator)

メソッドの概要

修飾子とタイプ	メソッド	説明
private Tree.IndexedSegmentTree.IndexedValue<T>[]	initArray(java.util.List<T> list, T initialValue)
(package private) Tree.IndexedSegmentTree.IndexedValue<T>	query(int left, int right)	クエリ クエリの区間を [left, right) の半開区間で渡すことに注意
(package private) Tree.IndexedSegmentTree.IndexedValue<T>	query(int left, int right, int begin, int end, int k)
(package private) void	update(int index, java.util.function.UnaryOperator<T> operator)	値の更新
(package private) void	update(int index, T value)	値の更新

クラスから継承されたメソッド java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

フィールドの詳細

internalArray

private final Tree.IndexedSegmentTree.IndexedValue<T>[] internalArray

exponent

private final int exponent

initialValue

private final Tree.IndexedSegmentTree.IndexedValue<T> initialValue

comparator

private final java.util.function.BinaryOperator<Tree.IndexedSegmentTree.IndexedValue<T>> comparator

コンストラクタの詳細

IndexedSegmentTree

IndexedSegmentTree(java.util.List<T> list,
                   T initialValue,
                   java.util.function.BinaryOperator<T> comparator)

IndexedSegmentTree

IndexedSegmentTree(int size,
                   T initialValue,
                   java.util.function.BinaryOperator<T> comparator)

メソッドの詳細

update

void update(int index,
            T value)

値の更新

パラメータ:

index - "0-indexed"のインデックス

value - 更新後の値

update

void update(int index,
            java.util.function.UnaryOperator<T> operator)

値の更新

パラメータ:

index - "0-indexed"のインデックス

operator - 更新式

query

Tree.IndexedSegmentTree.IndexedValue<T> query(int left,
                                              int right)

クエリ クエリの区間を [left, right) の半開区間で渡すことに注意

パラメータ:

left - "0-indexed"のクエリの左端

right - "0-indexed"のクエリの右端 + 1 つまり"1-indexed"のクエリの右端

戻り値:

クエリ結果

query

Tree.IndexedSegmentTree.IndexedValue<T> query(int left,
                                              int right,
                                              int begin,
                                              int end,
                                              int k)

initArray

private Tree.IndexedSegmentTree.IndexedValue<T>[] initArray(java.util.List<T> list,
                                                            T initialValue)