# Binary Indexed Tree


參考[OI Wiki](https://oi-wiki.org/ds/fenwick/) 這是一篇原理以及應用上非常詳盡的題解。

BIT / Fenwick tree / Binary indexed tree 是一個 lightweight 的 range query / point add 的資料結構，在實作難度跟常數上都能做到比線段樹更優，但是是個很玄的資料結構。

兩種操作的 TC 都是 $O(\log n)$

struct BIT {
    int n;
    vector<int> T;
    BIT(int n): n(n), T(n+1) {}
    BIT(const vector<int>& nums): BIT(nums.size()) {
        for (int i=1;i<=n;i++) {
            T[i] = nums[i-1];
            int j = i + (i&-i);
            if (j<=n) T[j] += T[i];
        }
    }
    void add(int i,int v) {
        i++;
        while (i<=n) {
            T[i] += v;
            i += i&-i;
        }
    }
    int query(int i) {
        i++;
        int ans = 0;
        while (i) {
            ans += T[i];
            i -= i&-i;
        }
        return ans;
    }
};

還可以寫得更短，

struct BIT {
    int n;
    vector<int> t;
	BIT(int n): n(n), t(n+1) {}
    void add(int i,int v) {
        for (i++;i>0;i+=i&-i) t[i] += v;
    }
    int query(int i) {
        int ans = 0;
        for (i++;i<=n;i-=i&-i) ans += t[i];
        return ans;
    }
};

我曾痴迷於將他的原理理解透徹，到最後才發現我的腦力還是不夠，Fenwick 的含金量還是太高。不妨看看 Codeforces 紅人 Colin Galen 的影片
[The Black Box Method: How to Learn Hard Concepts Quickly](https://www.youtube.com/watch?v=RDzsrmMl48I) 約在 3 分時就有提到其實連他本人都沒有完全了解原理，但這也不妨礙他的解題。所以在時機成熟前，就把它當黑箱，能拿來解題就行，不需過度執著原理。

## 二維 query

也就是 https://cses.fi/problemset/task/1739/
要處理子矩陣 query 以及 point add
作為模板，一棵樹如下

struct BIT {
	int m, n;
    vector<vector<int>> t;
	BIT(int m,int n): m(m), n(n), t(m+1,vector<int>(n+1)) {}
	void add(int i_,int j_,int v) {
		for (int i=i_+1;i<=m;i+=i&-i) {
			for (int j=j_+1;j<=n;j+=j&-j) t[i][j] += v;
		}
	}
	int query(int i_,int j_) {
		int ans = 0;
		for (int i=i_+1;i>0;i-=i&-i) {
			for (int j=j_+1;j>0;j-=j&-j) ans += t[i][j];
		}
		return ans;
	}
	int query(int mi,int mj,int Mi,int Mj) {
		return query(Mi,Mj) + query(mi-1,mj-1) - query(Mi,mj-1) - query(mi-1,Mj);
	}
};

操作的時間複雜度 $O(\log m \log n)$

## 一些怎樣都好的細節

一個常見的套路是用 BIT 當權值樹，也就是說（做值域壓縮後）把某個區間裡的數值存進 BIT 裡
就可以解類似 count reversed pair 的題目。

比方說 下面的題目：

* [LC reverse-pairs](https://leetcode.com/problems/reverse-pairs/description/)

（本題可以用歸併分治[另見 cdq 分治]或 BIT 求解。因為值域壓縮， $\times 2$ 的要求需要用二分搜達成）

* [LC count-increasing-quadruplets](https://leetcode.com/problems/count-increasing-quadruplets/description/)

(正解是 $O(n^2)$，但可以用 BIT 退而求其次做到 $O(n^2\log n)$)

* [LC minimum-inversion-count-in-subarrays-of-fixed-length](https://leetcode.cn/problems/minimum-inversion-count-in-subarrays-of-fixed-length/)

(CSES 有根本一樣的[題目](https://cses.fi/problemset/task/3223))

更甚者，有一個狂人想到了用兩顆 BIT 來解決 RMQ 問題的做法，常數比 segment tree 低得多，有興趣的話可以參見 [Cf 文章](https://codeforces.com/blog/entry/50903)。

## range add / range query

另外還有一種，使用兩顆 BIT 並且使用差分思想的巧妙方式去實現 $O(\log n)$，從此從 lazy segment tree 中解放，得到更低的常數！

but to do

## 有趣的習題

* 證明`add`, `query`的時間複雜度是$O(\log n)$

For `add`, since `i` grows atleast as fast as `lowbit(i)`, and that if `i=lowbit(i)`, `i` will be doubled in each loop, the loop terminates in $\log n$ time.
For `query`, in each loop, the last bit of `i` gets removed. There are atmost `2\log(i)` bits to remove.

* 證明`query`的有效性。

If `i=1`, we are done. Suppose this hold for any less `i`. Then
$$\begin{aligned}
query(i) &= T[i] + query(i-lowbit(i)) \\
&= sum(i-lowbit] + sum(0,i-lowbit(i)) \\
&= sum(0,i]
\end{aligned}$$

* 闡述 update tree 跟 interrogation tree的差別？

* 證明 $O(n)$ build方法之有效性。

我也不會

* 證明`add`的有效性。

* 證明或證偽，在 update tree 中，$i$ 有 $ctz(i)$ 個children，其中 $ctz$ 定義為："在二進制中，$i$ 前綴零的個數"

* 在heap及binary indexed tree中，因實作方式不同均存在 $O(n)$ 的及 $O(n\log n)$ 的構造方式。請比較兩者各自將 $O(n\log n)$ 進步到 $O(n)$ 的原理。