パッケージ library.ds.waveletmatrix

クラス WaveletMatrix

java.lang.Object
library.ds.waveletmatrix.WaveletMatrix
public final class WaveletMatrix extends Object
WaveletMatrix
関連項目:

  • コンストラクタの概要

    コンストラクタ
    コンストラクタ
    説明
    WaveletMatrix(int[] arr)
    コンストラクタ
    WaveletMatrix(int[] arr, int log)
    コンストラクタ
    WaveletMatrix(long[] arr)
    コンストラクタ
    WaveletMatrix(long[] arr, int log)
    コンストラクタ

  • メソッドの概要

    修飾子とタイプ
    メソッド
    説明
    final long
    get(int k)
    WaveletMatrix[k]を返す
    final long
    kthMax(int l, int r, int k)
    半開区間[l, r)に含まれる要素のうちk番目に大きい要素を返す
    final long
    kthMin(int l, int r, int k)
     
    final long
    next(int l, int r, long lower)
    半開区間[l, r)に含まれる要素のうちlowerの次に大きい要素を返す
    final long
    prev(int l, int r, long upper)
    半開区間[l, r)に含まれる要素のうちupperの次に小さい要素を返す
    final int
    rangeFreq(int l, int r, long upper)
    半開区間[l, r)に含まれる要素のうち[0, upper)である要素数を返す
    final int
    rangeFreq(int l, int r, long lower, long upper)
    半開区間[l, r)に含まれる要素のうち[lower, upper)である要素数を返す
    final int
    rank(int l, int r, long x)
    半開区間[l, r)に含まれるxの個数を返す
    final int
    rank(int r, long x)
    半開区間[0, r)に含まれるxの個数を返す

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

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

  • コンストラクタの詳細

    • WaveletMatrix

      public WaveletMatrix(int[] arr)
      コンストラクタ
      パラメータ:
      arr -

    • WaveletMatrix

      public WaveletMatrix(long[] arr)
      コンストラクタ
      パラメータ:
      arr -

    • WaveletMatrix

      public WaveletMatrix(int[] arr, int log)
      コンストラクタ
      パラメータ:
      arr -
      log -

    • WaveletMatrix

      public WaveletMatrix(long[] arr, int log)
      コンストラクタ
      パラメータ:
      arr - 配列
      log - 基本20で良い

  • メソッドの詳細

    • get

      public final long get(int k)
      WaveletMatrix[k]を返す
      パラメータ:
      k -
      戻り値:
      k番目の要素

    • rank

      public final int rank(int r, long x)
      半開区間[0, r)に含まれるxの個数を返す
      パラメータ:
      r -
      x -
      戻り値:
      半開区間[0, r)に含まれるxの個数

    • rank

      public final int rank(int l, int r, long x)
      半開区間[l, r)に含まれるxの個数を返す
      パラメータ:
      l -
      r -
      x -
      戻り値:
      半開区間[l, r)に含まれるxの個数

    • kthMin

      public final long kthMin(int l, int r, int k)
      パラメータ:
      l -
      r -
      k -
      戻り値:
      半開区間[l, r)に含まれる要素のうちk番目に小さい要素

    • kthMax

      public final long kthMax(int l, int r, int k)
      半開区間[l, r)に含まれる要素のうちk番目に大きい要素を返す
      パラメータ:
      l -
      r -
      k -
      戻り値:
      半開区間[l, r)に含まれる要素のうちk番目に大きい要素

    • rangeFreq

      public final int rangeFreq(int l, int r, long upper)
      半開区間[l, r)に含まれる要素のうち[0, upper)である要素数を返す
      パラメータ:
      l -
      r -
      upper -
      戻り値:
      半開区間[l, r)に含まれる要素のうち[0, upper)である要素数

    • rangeFreq

      public final int rangeFreq(int l, int r, long lower, long upper)
      半開区間[l, r)に含まれる要素のうち[lower, upper)である要素数を返す
      パラメータ:
      l -
      r -
      lower -
      upper -
      戻り値:
      半開区間[l, r)に含まれる要素のうち[lower, upper)である要素数

    • prev

      public final long prev(int l, int r, long upper)
      半開区間[l, r)に含まれる要素のうちupperの次に小さい要素を返す
      パラメータ:
      l -
      r -
      upper -
      戻り値:
      半開区間[l, r)に含まれる要素のうちupperの次に小さい要素

    • next

      public final long next(int l, int r, long lower)
      半開区間[l, r)に含まれる要素のうちlowerの次に大きい要素を返す
      パラメータ:
      l -
      r -
      lower -
      戻り値:
      半開区間[l, r)に含まれる要素のうちlowerの次に大きい要素