パッケージ library

クラス Tree.LazySegmentTree<T>

  • 含まれているクラス:
    Tree
    private static class Tree.LazySegmentTree<T>
extends java.lang.Object
    Lazy Segment Tree

    セグ木の基本操作に加えて，区間更新が O(logN) で行える

    • コンストラクタの概要

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

    • メソッドの概要

      すべてのメソッド インスタンス・メソッド concreteメソッド 
      修飾子とタイプ メソッド 説明
      private void evaluate​(int index)  
      private T[] initArray​(java.util.List<T> list, T initialValue)  
      private T[] initLazyArray​(T initialValue)  
      (package private) T query​(int left, int right)
      クエリ クエリの区間を [left, right) の半開区間で渡すことに注意
      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)
      値の更新
      (package private) void updateRange​(int left, int right, T value)
      区間更新 区間を [left, right) の半開区間で渡すことに注意
      private void updateRange​(int left, int right, T value, int begin, int end, int k)  

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

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

    • フィールドの詳細

      • internalArray

        private final T[] internalArray

      • lazyArray

        private final T[] lazyArray

      • exponent

        private final int exponent

      • initialValue

        private final T initialValue

      • comparator

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

    • コンストラクタの詳細

      • LazySegmentTree

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

      • LazySegmentTree

        LazySegmentTree​(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 - 更新式

      • updateRange

        void updateRange​(int left,
                 int right,
                 T value)
        区間更新 区間を [left, right) の半開区間で渡すことに注意
        パラメータ:
        left - "0-indexed"のクエリの左端
        right - "0-indexed"のクエリの右端 + 1 つまり"1-indexed"のクエリの右端
        value - 更新する値

      • updateRange

        private void updateRange​(int left,
                         int right,
                         T value,
                         int begin,
                         int end,
                         int k)

      • query

        T query​(int left,
        int right)
        クエリ クエリの区間を [left, right) の半開区間で渡すことに注意
        パラメータ:
        left - "0-indexed"のクエリの左端
        right - "0-indexed"のクエリの右端 + 1 つまり"1-indexed"のクエリの右端
        戻り値:
        クエリ結果

      • query

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

      • evaluate

        private void evaluate​(int index)

      • initArray

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

      • initLazyArray

        private T[] initLazyArray​(T initialValue)