树状数组

原理：

模板：

int[] tr = new int[];
int lowbit(int x) {
    return x & -x;
}
void add(int x, int u) {
    for (int i = x; i <= n; i += lowbit(i)) {
        tr[i] += u;
    }
}
int query(int x) {
    int ans = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        ans += tr[i];
    }
    return ans;
}

使用方法：

//原数组
nums
n = nums.length;
//初始化
for (int i = 0; i < n; ++i) add(i + 1, nums[i]);
//单点修改  改下标为index的值为value
public void update(int index, int val) {
    add(index + 1, val - nums[index]);
    //nums[index] = val;
}
//单点查询
public int sumRange(int index) {
    return query(index + 1) - query(index);
}
//区间查询
public int sumRange(int left, int right) {
    return query(right + 1) - query(left);
}
//区间修改
public void update(int left, int right, int u) {
    add(left + 1, u);
    add(right + 2, -u);
}