树状数组（Binary Indexed Tree）

树状数组常用于查询前缀和，前缀和通过差分可以得到区间和，并支持单点修改
单点修改和查询前缀和的时间复杂度均为(O(nlog_2 n))

假定有(a_1, a_2, ..., a_n)共n个数，我们使用数组bit[n+1] = {0}, 其中0位置不存储任何信息，仅作为边界判断

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

int sum(int i){
    int r = 0;
    while(i > 0){
        r += bit[i];
        i -= lowbit(i)
    }

    return r;
}

    void update(int i, int d){
        while(i <= n){
            bit[i] += d;
            i += lowbit(i)
        }
    }

    for(int i = 0; i < a.size(); i++)
        update(i + 1, a[i]);