Binary Index Tree

• 数组不变，区间查询：前缀和、树状数组、线段树；

• 数组单点修改，区间查询：树状数组、线段树；

• 数组区间修改，单点查询：差分、线段树；

• 数组区间修改，区间查询：线段树。

  链接

优质博客

模板

	// 上来先把三个方法写出来
{
    int[] tree;
    int lowbit(int x) {
        return x & -x;
    }
    // 查询前缀和的方法
    int query(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += tree[i];
        return ans;
    }
    // 在树状数组 x 位置中增加值 u
    void add(int x, int u) {
        for (int i = x; i <= n; i += lowbit(i)) tree[i] += u;
    }
}

// 初始化「树状数组」，要默认数组是从 1 开始
{
    for (int i = 0; i < n; i++) add(i + 1, nums[i]);
}

// 使用「树状数组」：
{   
    void update(int i, int val) {
        // 原有的值是 nums[i]，要使得修改为 val，需要增加 val - nums[i]
        add(i + 1, val - nums[i]); 
        nums[i] = val;
    }
    
    int sumRange(int l, int r) {
        return query(r + 1) - query(l);
    }
}

307. 区域和检索 - 数组可修改

方法一：树状数组

class NumArray {
    
    int n;
    int[] tree, nums;

    int lowbit(int x) {
        return x & -x;
    }
    // 查询前缀和的方法
    int query(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) ans += tree[i];
        return ans;
    }
    // 在树状数组 x 位置中增加值 u
    void add(int x, int u) {
        for (int i = x; i <= n; i += lowbit(i)) tree[i] += u;
    }
    void init(int[] nums) {
        tree = new int[nums.length + 1];
        for (int i = 0; i < nums.length; ++i)
            add(i + 1, nums[i]);
    }

    public NumArray(int[] nums) {
        this.nums = nums;
        n = nums.length;
        init(nums);
    }
    
    public void update(int index, int val) {
        add(index + 1, val - nums[index]);
        nums[index] = val;
    }
    
    public int sumRange(int left, int right) {
        return query(right + 1) - query(left);
    }
}

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray obj = new NumArray(nums);
 * obj.update(index,val);
 * int param_2 = obj.sumRange(left,right);
 */