Binary Indexed Tree

Binary indexed tree is a kind of data that use mostly to handle questions like “get the sum from indexes x to y of array”; It pre-processes all data in another array for query purpose.

One of the key functions is to get the lowest binary “1” bit. (lowBit())
For example: given number “15”, which in binary is “1111”,
lowBit function will return lowest bit that is “1”,  which is “0001” in this case.
The easiest way to do this is shown below:

private int lowBit(int idx) {
	// 1111 & 0001
	return idx & (-idx);
}

Note that all operation is Non-zero-base. Idx starts from 1.
Basically the concept is to pre-process sums into blocks.
For example: To get the sum of arr[1~10], we have:

S[10] = arr[10 – 1] + S[9] + S[8];

9: 1001

8: 1000

Here shows the code for basic operations:

public class BinaryIndexTree {
	int[] tree;
	int[] arr;
	public BinaryIndexTree(int[] arr) {
		if (arr == null || arr.length == 0) return;
		this.arr = arr;
		build();
	}
	
	private void build() {
		this.tree = new int[arr.length + 1];
		for (int i = 1; i <= arr.length; i++) { 
			tree[i] += arr[i - 1]; 
			for (int j = i - 1; j > i - lowBit(i); j -= lowBit(j))
				tree[i] += tree[j];
		}
	}
	
	public void update(int idx, int val) {
		this.arr[idx - 1] = val;
		for (int i = idx; i <= arr.length; i++) { 
			tree[i] = arr[i - 1]; 
			for (int j = i - 1; j > i - lowBit(i); j -= lowBit(j))
				tree[i] += tree[j];
		}
	}
	
	private int lowBit(int idx) {
		return idx & (-idx);
	}
	
	public int getSum(int idx) {
		int sum = 0;
		while (idx > 0) {
			sum += tree[idx];
			idx -= lowBit(idx);
		}
		return sum;
	}
	
	
	public int getSum(int fromIdx, int toIdx) {
		return getSum(toIdx) - getSum(fromIdx) + arr[fromIdx - 1];
	}
	
	
	public String toString() {
		StringBuilder sb = new StringBuilder();
		for (int i : this.arr) {
			sb.append(i);
			sb.append(" ");
		}
		sb.append("n");
		for (int i : this.tree) {
			sb.append(i);
			sb.append(" ");
		}
		sb.append("n");
		return sb.toString();
	}
	
	
	public static void main(String[] args) {
		int[] arr = new int[] {2,3,6,5,3,7,4,3};
		BinaryIndexTree inst = new BinaryIndexTree(arr);
		System.out.println(inst.toString());
		System.out.println(inst.getSum(3, 5));
		inst.update(3, 3);
		System.out.println(inst.toString());
		System.out.println(inst.getSum(3, 5));
	}
}

Output:
2 3 6 5 3 7 4 3 
0 2 5 6 16 3 10 4 33 
14

2 3 3 5 3 7 4 3 
0 2 5 3 13 3 10 4 30 
11

References:

Topcoder-Binary Indexed Tree

WIKI Chinese-Binary Indexed Tree