IndexTree

标签：index arr int IndexTree num public

IndexTree 树状数组

功能：计算子数组累加和，支持单点变动

public class IndexTree {
    int N;
    int[] arr;

    public IndexTree(int N) {
        this.N = N + 1;
        arr = new int[N + 1];
    }

    // 在原始数组index位置的值+num
    public int add(int index, int num) {
        while (index < N) {
            arr[index] += num;
            index += index & -index;
        }
    }

    // 求原始数组arr[0， index]的累加和
    public int sum(int index) {
        int res = 0;
        while (index > 0) {
            res += arr[index];
            index -= index & -index;
        }
        return res;
    }
}

标签：index,arr,int,IndexTree,num,public
From： https://www.cnblogs.com/annamaple/p/17352626.html