フェニック木(Binary Indexed Tree)

[アルゴリズム,GeeksforGeeks,RMQ]

練習のための問題は 競技プログラミングの履歴、LSB(least significant bit)については二進展開（ＭＳＢ/ＬＳＢ）で

フェニック木(Binary Indexed Tree)

フェニック木は1993年にピーター・フェニックにより提案された木構造です。

フェニック木を使えば、今まで累積和を使って計算したような区間の和がある程度少ない実装で高速に実行できるようです。

この構造のキモは「区間の和を求める際にすべての区間の値をそのまま持たないほうが早く計算できね？」→「和を木構造に配置して取り出すときは親をたどって足し算するようにしたわ」みたいな感じ

フェニック木で使う操作は以下の通り、正直プログラミング的には元の名称はイマイチですね…

  詳しい解説

• Binary Indexed Tree もしくはフェニック木について
  • Wikipedia - フェニック木 概要

• 有志のスライド
  • Binary indexed tree
    • こっちのほうがわかりやすい、区間の和まではこれで理解できる

• Binary Indexed Tree のはなし - hos.ac
  • 頭いい人向け、フェニック木上での二分探索までわかる

• LSB(least significant bit)
  • Find first and last set bit of a long integer
  • Wikipedia - Find first set
  • Wikipedia - Bit numbering
  • Wikipedia - 最下位ビット

• 参考
  • anctgcc’s diary - 小学生でもわかる累積和と中学生でもわかるBinary Indexed Tree

• 原文
  • Peter M. Fenwick. A new data structure for cumulative frequency tables. Software - Practice and Experience, 24(3):327--336, March 1994.

フェニック木(区間の和)

  解説(GeeksForGeeks)

• 翻訳元
  • Binary Indexed Tree or Fenwick Tree

Binary Indexed Tree もしくはフェニック木について

Binary Indexed Treeを理解するために次の問題について考えてみましょう。

ある配列 arr[0...n-1] があるとしましょう、これを以下のように操作する必要があります

1. 最初のi番目までの和を求める
2. 0 <= i <= n-1の範囲で、arr[i] = x のように指定された要素を更新する

これについての単純な解法は、0からi-1まで巡回して要素の和を計算することです。値を更新するためには、arr[i] = xを実行すればよいです。最初の操作はO(n)の時間がかかり、そして次の操作はO(1)の時間がかかります。(訳者注：素朴な全探索）

次の単純な解法は、もう一つの配列を作成し最初からi番目までの和をその配列の同じインデックスに保存しておくというものです。与えられた範囲の和はこれでO(1)の時間で計算できますが、更新の操作にはO(n)時間がかかってしまいます。これは実行するクエリが膨大で、更新が少ない場合に有効です。(訳者注：累積和）

この両方の操作に対してO(log n)時間で処理を行うことは可能でしょうか？有効な解決策はセグメント木を使うことです。これはどちらの操作もO(log n)時間で行うことができます。

Binary Indexed Tree（以下、フェニック木）を使うことで、両方の操作に対してO(log n)時間で処理を行うことができます。セグメント木よりもフェニック木が有用な点は、実装が容易でメモリ空間をとらないことです。。。

説明

フェニック木は１つの配列で表現されます。配列名を@bit[]としましょう。フェニック木のそれぞれのノードは与えられた配列のいくつかの要素の和を保存します。フェニック木のサイズは入力値の配列とおなじです。以下のコードでは、実装の簡単化のためにサイズはn+1としている。

構造

フェニック木の初期化の際、@bit[]はすべて０で埋めます。次に更新操作を呼び、すべてのインデックスに実際の和を入れていきます。更新の操作の方法については、下のほうで議論します。

操作

sum

sum(index): arr[0..index]の和を返す

 arr[0..index]の和を返す時には@bit[0..n]を使用する。
 これは、@bit[]が与えられた配列arr[0..n-1]で構築されていることを前提としている。

(1) 和を0で初期化し、インデックスはインクリメントする
(2) インデックスが０以上である限り以下を繰り返す

...(a) @bit[index]の値を返却するsumに加える
...(b) @bit[index]の親を辿る。親のノードはインデックス値からLSB(last set bit)を除くことで手に入る。
       i.e. index = index - (index & (-index))


(ex) index = 7(=00000111), LSB(7)=1 なので  00000111から1番目のbitを削除
     index = 6(=00000110), LSB(6)=2 なので  00000110から2番目のbitを削除
     index = 4(=00000100), LSB(4)=3 なので  00000100から3番目のbitを削除
     index = 0(=00000000), 0は最上の親要素なのでループ終了

以下の図はgetSum()がどのように動作するか示したものです。以下のような重要な観察が得られます。

• インデックス＝０のノードはダミー
• インデックスyのノードはインデックスxのノードの親
  • yはxの２進数表現からLSBを削除してやると取得できる
• xのノードの子yは、yを除いたxの要素の和を保持する

add

add(index, val): '''arr[index] += val'''という操作によりフェニック木を更新する
 配列arr[]はここでは変更されない、この操作は@bit[]を変更するのみである。
(1) インデックスをインクリメントする
(2) インデックスがN以下である限り以下を繰り返す
...(a) @bit[index]に値を加算
...(b) @bit[index]の親に遷移。親のノードはインデックス値からLSB(last set bit)を除くことで手に入る。

  練習問題

AOJ DSL_2_B

• Range Query - Range Sum Query (RSQ) - Aizu Online Judge
  • 回答のコード #2942008 Solution for DSL_2_B by hiroyuking
  • 0-indexedかそうでないかでハマった

よくわからない自分のための注釈

• とりあえずソースコードは以下

class FenwickTree
  attr_accessor :n, :array, :bit

  def initialize(n, array = nil)
    @n = n
    @bit = Array.new(@n+1, 0)
    if array.nil?
      @array = Array.new(@n,0)
    else
      @array = array.dup
    end
    for i in 0..n
      add(i,@array[i])
    end
  end

  def sum(idx)
    ans = 0
    idx += 1
    while not idx.zero?
      ans += @bit[idx]
      least = idx&-idx
      idx -= least
    end
    ans
  end

  def range(left, right)
    if left > right
      0
    else
      sum(right)-sum(left-1)
    end
  end

  def add(idx, x)
    idx += 1
    while idx <= @n
      @bit[idx] += x
      least = idx&-idx
      idx += least
    end
  end
end

• 具体例として以下のような木を作ってみる

• コードだと以下のような感じ

a = [5,3,7,9,6,4,1,2]
ft = FenwickTree.new(a.length, a)
p ft.bit
# [0, 5, 8, 7, 24, 6, 10, 1, 37]

• sumの結果、区間0～nまでの和が正しく計算できた

フェニック木(ある値Wよりも大きい区間和)

  解説(Fenwickの論文から)

• 翻訳元
  • A new data structure for cumulative frequency tables

操作

• GeeksForGeeksには解説がないので、いろいろ調べて日本語化

lower_bound

lower_bound(w): 区間0〜Nまでの範囲において、ある値Wよりも大きい区間和の最初のインデックスを返す

 すでに構築済みの変数に加えて、@n2を使用する。
 これは、フェニック木の構築時に作成する配列の要素数Nよりも小さい最大の２のべき乗
 例えば配列の要素数が16であれば8がその数になる。

(1) インデックスを０で初期化、マスクを@n2で初期化
(2) マスクが０でない限り以下を繰り返す

...(a) インデックス値とマスクの和をテストインデックス(tidx)として定義
...(b) もし@bit[tidx]よりWの値が大きければ
　　　　・インデックスをテストインデックスの値で上書き
　　　　・Wから@bit[tidx]の値を引く
...(c) マスクを２で割る

• とりあえずソースコードは以下

#*******************************************************************/
#* Add binary search method
#*******************************************************************/
class FenwickTree
  attr_accessor :n, :n2, :array, :bit

  def initialize(n, array)
    @n = n
    n2 = 1
    while n2 < n
      # prepare smallest exponent of 2 larger than N
      # With the 16-element table of the examples here,
      # the initial value of Mask would be 8
      n2 <<= 1
    end
    @n2 = n2 >>= 1
    @bit = Array.new(@n+1, 0)
    @array = array.dup
    for i in 0..n
      add(i,@array[i])
    end
  end

  def sum(idx)
    ans = 0
    idx += 1
    while not idx.zero?
      ans += @bit[idx]
      least = idx&-idx
      idx -= least
    end
    ans
  end

  def range(left, right)
    if left > right
      0
    else
      sum(right)-sum(left-1)
    end
  end

  def add(idx, x)
    #puts "add idx=#{idx} := #{x}"
    idx += 1
    while idx <= @n
      @bit[idx] += x
      #puts "@bit[#{idx}] += #{x} == #{@bit[idx]}"
      #p @bit
      least = idx&-idx
      idx += least
    end
  end

  def lower_bound(w)
    idx,mask = 0,@n2
    while mask != 0
      #puts "idx=#{idx},mask=#{mask}"
      tidx = idx + mask
      if w >= @bit[tidx]
        idx = tidx
        w = w - @bit[idx]
      end
      mask = mask / 2
    end
    idx
  end
end

  練習問題

AOJ DSL_3_C

• Sliding Window - The Number of Windows - Aizu Online Judge

フェニック木(区間の最小値)

  解説(xxx)

• 翻訳元
  • Efficient Range Minimum Queries using Binary Indexed Trees

CodeForcesに有志見つけた論文上げてた　→　How to use Binary Indexed Tree for Range Min/Max Query?

2.2 BITを定義する

フェニック木（左右どちらの形式の木構造にしても）は２のK乗のノードを持ち、その高さはKです。

もしその配列のインデックスをバイナリで管理するとしたら

• 左二項木(left binomial tree)であるところのBIT1は
  • 親ノード(i) = i + 2のLSB(i)乗

• 右二項木(right binomial tree)であるところのBIT2は
  • 親ノード(i) = i - 2のLSB(i)乗

def lsb(n)
  n&-n
end

# left
def parent_l(n)
  n -= lsb(n)
  n
end

# right
def parent_r(n)
  n += lsb(n)
  n
end

p parent_l(7) #=> 6
p parent_r(7) #=> 8

これにより、左右どちらの木構造にしても探索がlogNになる

（訳者注）：いままで作ってたのは左二項木になる

2.3 クエリ操作

インデックスi, j、配列 1 <= i <= j <= N が与えられるとする。このときA[i], A[i+1], ... , A[j]のうち最小値が何か？という問いに答えたい。まずは最初の木のノードiから親を辿り始め、そのインデックスがj以下になるまでできるだけ処理を進める。同じことを２番目に用意した木で実施し、ノードjから親を辿る。どちらの場合でも、私たちは同じノードに至り、それにより配列はA[i ... j]という部分列に分けられる、これは用意した両方の木にあるし、探索が終了した共通のノードにも見つかる。

部分列A[5 ... 13]に対するクエリ操作により、これの例示をします。

ノード５から探索を始め、探索中のノードのインデックスが13以下になるまでそれを続けます。その次のノード８のインデックスは16で、これは13より大きいためそこで探索を終了します。ですので、ここで作成した部分列には14, 15, 16は含まれない。ここまでで、探索はノード5,6,8を通った。ここまでで2つ目の木にて見つかるノード5,6について最小の値を取得した。図２を見ると、ノード5はA[5]の最小値を保持しノード6はA[6 ... 7]までの最小値を保持する。同様にして、2つ目の木にてノード13から探索を開始し、ノード13,12,8を通る。先ほど１つ目の木にてノード13,12の最小値を取得したはずです。図１を見るとノード12はA[9 ... 12]の最小値を保持しノード13はA[13]の最小値を保持する。

ここで得られる観察としては、A[5 ... 13]という配列は以下のような部分列に分割された：

A[5 ... 5], A[6 ... 7], A[8], A[9 ... 12], A[13]

これの重要なところは、そのどちらの探索にもノード8が含まれていることです。これが常に起きることを証明します：（証明略）

まとめ

• 要は指定された範囲で両方の端から探索すると絶対最小値が見つかるようです

操作

• How to adapt Fenwick tree to answer range minimum queries

min

min(left,right): 区間left〜rightまでの範囲における最小の区間の値を返す

 まず左手、次に右手、最後にBITと実際の値を比較して返す

(1) val を無限で初期化
(2) インデックス(=idx)をleftで初期化
(3) インデックス(=idx)がright以下の限り,(a)以下をループ

...(a) val に @bit[idx] と valを比較して小さいものを上書き
...(b) i を 右二項木 の方法で親を辿り上書き

(4) インデックス(=idx)をrightで初期化
(5) インデックス(=idx)がleft以上の限り,(a)以下をループ

...(a) val に @bit[idx] と valを比較して小さいものを上書き
...(b) i を 左二項木 の方法で親を辿り上書き

(6) val と @array[i] を小さいものを上書き
(7) valが区間最小値なのでリターン

• とりあえずソースコードは以下

  def lsb(n)
    n&-n
  end

  # left
  def parent_l(n)
    n -= lsb(n)
    n
  end

  # right
  def parent_r(n)
    n += lsb(n)
    n
  end

  def min(l,r)
    puts "#{l} to #{r}"
    val = Float::INFINITY
    i = l
    while parent_r(i) <= r
      val = [val, @bit[i]].min
      i = parent_r(i)
    end
    i = r
    while parent_l(i) >= l
      val = [val, @bit[i]].min
      i = parent_l(i)
    end
    val = [val, @array[i]].min
    val
  end