BinaryIndexedTree.java

package algorithm.tree;

/**
 * Created by Jinseoung on 2016-12-27.
 */
public class BinaryIndexedTree {

    int[] numbers, tree;

    /* how to get last binary number
     *
     * -b = ~b + 1
     * b      = 00001010
     * -b     = 11110110
     * b & -b = 00000010 // last binary number
     */

    public BinaryIndexedTree(int[] numbers) {
        // temp for first update
        this.numbers = new int[numbers.length];
        this.tree = new int[numbers.length];

        for(int i = 0 ; i < this.tree.length; i++) {
            update(i, numbers[i]);
        }
        this.numbers = numbers;
    }

    public void update(int index, int update) {
        int diff = update - numbers[index];
        numbers[index++] = update;

        while (index <= this.numbers.length) {
            tree[index-1] += diff;
            index += (index & -index);
        }
    }

    public int sum(int index) {
        index++;
        int answer = 0;
        while (index > 0) {
            answer += tree[index-1];
            index -= (index & -index);
        }
        return answer;
    }

    public static void main(String[] args) {
        BinaryIndexedTree bit = new BinaryIndexedTree(new int[]{1,2,3,4,5,6});

        System.out.println(bit.sum(2)); // 6
        System.out.println(bit.sum(3)); // 10
        System.out.println(bit.sum(4)); // 15

    }
}