読者です 読者をやめる 読者になる 読者になる

kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

Fenwick tree, binray indexed tree(BIT)

Algorithm

リポジトリ
Fenwick tree, binray indexed tree(BIT)
 x_0, x_1, \cdots , x_{n-1}
が与えられたとき、

  •  O(\log n)累積和 sum(k)=\sum_{i=0}^k x_i
  •  O(\log n)加算更新 add(i, a)=x_{i}\leftarrow x_{i}+a

の操作ができるデータ構造で、空間計算量は O(n)、構築にかかる計算量は(n回addするので) O(n\log n)
当然だが(頻繁に)更新を行わないのであれば、普通に S_i = x_i + S_{i-1}でテーブル作った方がいい。

葉が x_0, x_1, \cdots , x_{n-1}に相当する。親は子の要素を足した値を保持する。
ここで、下図の点線のノードは不要で使用せず、実線のノードだけを使う。
葉の下の数字はノード番号(1スタートさせることも多々あるが、実装は0スタートの物にした)。
累積和 sum(k)は、ノード kから左上のノードを足していく。
加算更新 add(i,a)は、ノード iから親ノードに aを順次加えていく。
FenwickTree

実装は非常にラク。インデクスを1スタートにすると、カレントノードの遷移が(j&-j)を加算/減算するだけで分かりやすい。
ちなみに(j&-j)は、2進数表示で考えたとき、jの下位bit(右)から見て一番始めに1がたっているところだけ1それ以外は0の数。

public final class FenwickTree{
	private int[] x;
	public FenwickTree(int n){ init(n);}
	public FenwickTree(int[] x){ init(x, 0, x.length);}
	public FenwickTree(int[] x, int begin, int end){ init(x, begin, end); }
        /** all 0, O(n) n:=x.length */
	public final void init(int n){ x = new int[n]; Arrays.fill(x, 0); }
	/** O(n log n) n:=x.length */
	public final void init(int[] x){ init(x, 0, x.length); }
	/** O(n log n) n:=x.length */
	public final void init(int[] x, int begin, int end){
		this.x = new int[end - begin];
		System.arraycopy(x, begin, this.x, 0, end - begin);
	}
	/**
	 * Gets summation from x[0] to x[i] O(log n) n:=x.length<br>
	 * @param i	(inclusive) end index
	 * @return	x[0] + x[1] + ... + x[i]
	 */
	public final int sum(int i){
		int ret = 0;
		//If 1 start (not 0 start), use j -= (j&-j)
		for(int j = i; j >= 0; j = ((j & (j+1)) - 1)) ret += x[j];
		return ret;
	}
	/**
	 * Gets summation from x[i] to x[j] (※i <= j) O(log n) n:=x.length
	 * @param i (inclusive) start index
	 * @param j (inclusive) end index
	 * @return  x[i] + x[i+1] + ... + x[j]
	 */
	public final int sum(int i, int j){ return i == 0 ? sum(j) : sum(j) - sum(i-1); }
	/**
	 * x[i] += a O(log n) n:=x.length<br>
	 * @param i target index
	 * @param a	
	 */
	public final void add(int i, int a){
		//If 1 start (not 0 start), use j += (j&-j)
		for(int j = i; j < x.length; j |= j+1) x[j] += a;
	}
}