維基百科： 樹狀數(shù)組或二叉索引樹（英語：Binary Indexed Tree），又以其發(fā)明者命名為Fenwick樹，最早由Peter M. Fenwick于1994年以A New Data Structure for Cumulative Frequency Tables為題發(fā)表在SOFTWARE PRACTICE AND EXPERIENCE。

其初衷是解決數(shù)據(jù)壓縮里的累積頻率（Cumulative Frequency）的計(jì)算問題，現(xiàn)多用于高效計(jì)算數(shù)列的前綴和， 區(qū)間和。

算法精妙之處：

• lowbit()函數(shù)：返回二進(jìn)制輸入值最低位的1，如：11100==>100

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

利用上面的函數(shù)我們就可以構(gòu)建出樹狀數(shù)組：

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

輸入：

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

• input的樹狀數(shù)組：R為邊界

• 構(gòu)建樹狀數(shù)組：

構(gòu)建樹狀數(shù)組

• 更新數(shù)組update(i, delta)：sum[i] += delta

示例update(2, 3)：關(guān)注第2個(gè)和第4個(gè)結(jié)點(diǎn)的變化

update

• 查詢前綴和query(i)：查詢第 i 個(gè)的前綴和

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

Query

• 時(shí)間復(fù)雜度：構(gòu)建：O（N）、更新和查詢：O（logN）

• 空間復(fù)雜度：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; }
};

試著挑戰(zhàn)一下leetcode上面的題目吧 ；）
小和問題：https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self/
區(qū)間和個(gè)數(shù)：https://leetcode-cn.com/problems/count-of-range-sum/

參考：

維基百科

動(dòng)態(tài)圖來源