传送门
树状数组板子题。借这道题整理一下树状数组的模板

class NumArray {
private:
    vector<int> tree;
    vector<int> arr;
    int n;

    int lowbit(int x) {
        return x & -x;
    }

    // 求前缀和
    // [0, x)
    int query(int x) {
        int res = 0;
        for (int i = x; i > 0; i -= lowbit(i)) {
            res += tree[i];
        }
        return res;
    }

    // 单点x增加u
    void modify(int x, int u) {
        for (int i = x; i <= n; i += lowbit(i)) {
            tree[i] += u;
        }
    }
public:
    NumArray(vector<int>& nums) : tree(nums.size() + 1), arr(nums) {
        // 初始化tree
        // 默认下标从1开始
        n = nums.size();
        for (int i = 0; i < n; i++) {
            modify(i + 1, arr[i]);
        }
    }

    void update(int index, int val) {
        modify(index + 1, val - arr[index]);
        arr[index] = val;
    }

    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);
 */

树状数组模板整理如下：

// 计算下标
int lowbit(int x) {
    return x & -x;
}

// 求前缀和
// [0, x)
int query(int x) {
    int res = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        res += tree[i];
    }
    return res;
}

// 单点x增加u
void modify(int x, int u) {
    for (int i = x; i <= n; i += lowbit(i)) {
        tree[i] += u;
    }
}

初始化如下:

// 下标偏移1位，默认从1开始
for (int i = 0; i < n; i++) {
    modify(i + 1, arr[i]);
}