パッケージ library

クラス Tree.SegmentTree<T>

java.lang.Object

library.Tree.SegmentTree<T>

含まれているクラス:

Tree

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

Segment Tree

モノイドに対する値の更新，区間に対するクエリをそれぞれO(log n)で行える．
更新，クエリの引数は 0-indexed で渡すことに注意

フィールドの概要

フィールド

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

コンストラクタの概要

コンストラクタ

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

メソッドの概要

修飾子とタイプ	メソッド	説明
private T[]	initArray(java.util.List<T> list, T initialValue)
(package private) T	query(int left, int right)	クエリ クエリの区間を [left, right) の半開区間で渡すことに注意
(package private) 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 T[] internalArray

exponent

private final int exponent

initialValue

private final T initialValue

comparator

private final java.util.function.BinaryOperator<T> comparator

コンストラクタの詳細

SegmentTree

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

SegmentTree

SegmentTree(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

T query(int left,
        int right)

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

パラメータ:

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

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

戻り値:

クエリ結果

query

T query(int left,
        int right,
        int begin,
        int end,
        int k)

initArray

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