パッケージ library.ds.fenwicktree

クラス FenwickTree

java.lang.Object
library.ds.fenwicktree.FenwickTree
public final class FenwickTree extends Object
FenwickTree(Binary Indexed Tree[BIT])
関連項目:

  • コンストラクタの概要

    コンストラクタ
    コンストラクタ
    説明
    FenwickTree(int sz)
    コンストラクタ
    FenwickTree(int[] a)
    コンストラクタ
    FenwickTree(long[] a)
    コンストラクタ

  • メソッドの概要

    修飾子とタイプ
    メソッド
    説明
    final void
    add(int l, int r, long x)
    閉区間[l, r]に値を加算する
    final void
    add(int k, long x)
    k番目に値を加算
    final long
    get(int k)
    FenwickTree[k]を返す
    final int
    lowerBound(long w)
    閉区間[0, k]の区間和がw以上となるような最小のk
    final long
    sum(int k)
    閉区間[0, k]の和を返す
    final long
    sum(int l, int r)
    閉区間[l, r]の和
    final long[]
    toArray()
    FenwickTreeの累積和を返す
    final String
    toString()
     
    final int
    upperBound(long w)
    閉区間[0, k]の区間和がwよりも大きくなるような最小のk

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

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

  • コンストラクタの詳細

    • FenwickTree

      public FenwickTree(int sz)
      コンストラクタ
      パラメータ:
      sz - サイズ

    • FenwickTree

      public FenwickTree(int[] a)
      コンストラクタ
      パラメータ:
      a - int型の配列

    • FenwickTree

      public FenwickTree(long[] a)
      コンストラクタ
      パラメータ:
      a - long型の配列

  • メソッドの詳細

    • sum

      public final long sum(int k)
      閉区間[0, k]の和を返す
      パラメータ:
      k -
      戻り値:
      閉区間[0, k]の和

    • sum

      public final long sum(int l, int r)
      閉区間[l, r]の和
      パラメータ:
      l -
      r -
      戻り値:
      閉区間[l, r]の和

    • get

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

    • add

      public final void add(int k, long x)
      k番目に値を加算
      パラメータ:
      k -
      x -

    • add

      public final void add(int l, int r, long x)
      閉区間[l, r]に値を加算する
      パラメータ:
      l -
      r -
      x -

    • lowerBound

      public final int lowerBound(long w)
      閉区間[0, k]の区間和がw以上となるような最小のk
      パラメータ:
      w -
      戻り値:
      [0, k]の区間和がw以上となるような最小のk

    • upperBound

      public final int upperBound(long w)
      閉区間[0, k]の区間和がwよりも大きくなるような最小のk
      パラメータ:
      w -
      戻り値:
      [0, k]の区間和がwよりも大きくなるような最小のk

    • toArray

      public final long[] toArray()
      FenwickTreeの累積和を返す
      戻り値:
      FenwickTreeの累積和

    • toString

      public final String toString()
      オーバーライド:
      toString クラス内 Object