维基百科： 树状数组或二叉索引树（英语：Binary Indexed Tree），又以其发明者命名为Fenwick树，最早由Peter M. Fenwick于1994年以A New Data Structure for Cumulative Frequency Tables为题发表在SOFTWARE PRACTICE AND EXPERIENCE。

其初衷是解决数据压缩里的累积频率（Cumulative Frequency）的计算问题，现多用于高效计算数列的前缀和， 区间和。

算法精妙之处：

• lowbit()函数：返回二进制输入值最低位的1，如：11100==>100

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

利用上面的函数我们就可以构建出树状数组：

例如：值得注意的是以1开始

输入：

input[i] = { 8, 9, 35, 5, 8, 47 }

• input的树状数组：R为边界

• 构建树状数组：

构建树状数组

• 更新数组update(i, delta)：sum[i] += delta

示例update(2, 3)：关注第2个和第4个结点的变化

update

• 查询前缀和query(i)：查询第 i 个的前缀和

示例query(6)：即sum[4] + sum[5] + sum[6]

Query

• 时间复杂度：构建：O（N）、更新和查询：O（logN）

• 空间复杂度：O（N）

Talk is cheap. Show me the code!

#include <bits/stdc++.h>
using namespace std;

class FenwickTree {
public:
    FenwickTree(int n) : sum(n + 1, 0) {}

    void update(int i, int delta) {
        while (i < sum.size()) {
            sum[i] += delta;
            i += lowbit(i);
        }
    }

    int query(int i) {
        int s = 0;
        while (i < sum.size()) {
            s += sum[i];
            i -= lowbit(i);
        }
        return s;
    }

private:
    vector<int> sum;
    static inline int lowbit(int x) { return x & -x; }
};

试着挑战一下leetcode上面的题目吧 ；）
小和问题：https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/
区间和个数：https://leetcode-cn.com/problems/count-of-range-sum/

参考：

维基百科

动态图来源