BinaryIndexedTree求解指定范围和

import java.util.Arrays;

public class BinaryIndexedTree {
    int N;
    int[] tree;
    int[] input;

    public BinaryIndexedTree(int[] input) {
        this.input = input;
        this.N = this.input.length;
        this.tree = new int[treeSize()];
        init();
    }

    /**
     * 计算构造Binary Indexed Tree的一维数组大小
     *
     * @return
     */
    int treeSize() {
        int size = 1;
        while (size < N) size <<= 1;
        return size + 1; // +1是因为indexed tree的下标从1开始，0为无效的位
    }

    /**
     * 初始化构造Binary Indexed Tree
     */
    void init() {
        // indexed tree下标从0开始，并且0位无效
        for (int i = 1; i <= input.length; i++) update(i, input[i - 1]);
    }

    /**
     * 更新指定位置的数值
     *
     * @param index Binary Indexed Tree的元素索引。即，输入数组的的索引+1。如果输入数组的索引从1开始有效，则可以直接使用其索引。<br/>
     *              索引从1开始
     * @param abs   指定位置的变更值=修改后的值-变更前的值
     */
    void update(int index, int abs) {
        while (index < tree.length) {
            tree[index] += abs;
            index += lowBit(index);
        }
    }

    /**
     * 计算前N项和，index从1开始计数
     */
    int sum(int index) {
        int sum = 0;
        while (index > 0) {
            sum += tree[index];
            index -= lowBit(index);
        }
        return sum;
    }

    /**
     * 计算a到b的和（包含a和b）<br/>
     * a和b均从0开始
     */
    int between(int a, int b) {
        // 转换成Binary Indexed Tree下标
        int from = Math.min(a, b) + 1;
        int to = Math.max(a, b) + 1;
        return sum(to) - sum(from - 1); // 包含b
    }

    /**
     * 计算低位值
     */
    int lowBit(int index) {
        return index & (-index);
    }

    // test code below

    public static void main(String[] args) {
        int[] input = new int[10];
        Arrays.fill(input, 1);
        BinaryIndexedTree bit = new BinaryIndexedTree(input);

        bit.update(4, 1);
        bit.update(9, 10);

        System.out.println(bit.tree.length);
        System.out.println("==============");
        System.out.println(bit.between(1, 2));
        System.out.println(bit.between(3, 5));
        System.out.println(bit.between(3, 9));
        System.out.println(bit.between(0, 9));
    }
}