樹狀數組(Binary Index Tree)

• 英文名：使用二進制下標的樹結構

• 理解：這個樹實際上用數組來存，二進制下標就是將正常的下標拆為二進制來看。

求x的最低位1的函數lowbit（x）

• 假設x的二進制表示為x= ...10000，其中1是x的最低位1，前面的位數我們不關心。則-x=.....01111+1=10000(取反+1)。
• x&-x=...10000&..01111+1=000000...10000，因此我們可以得到x的最低位1所對應的那個數。

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

樹狀數組的理解

• t[pos]的含義：t[pos]=∑{?x∣x+lowbit(x)=pos}t[x]+a[pos]t[pos]=\sum_{\{\forall x \mid x+lowbit(x)=pos\}}{t[x]}+a[pos]t[pos]=∑{?x∣x+lowbit(x)=pos}?t[x]+a[pos]。
• 例如：$t[8=1000]=t[4=0100]+t[6=0110]+t[7=0111]+a[8]$，其中$a[8]$是原始數組第8個數。
• 注意：不能通過$pos?lowbit(pos)$得到x。
  

建樹

• 由于不能通過$pos?lowbit(pos)$反過來確定x，所以我們要從x開始累加lowbit(x)向上更新，這一步相當于前綴和的累積。

void build(int pos,int val) {while (pos<=n) {t[pos] += val;pos += lowbit(pos);}
}

查詢

• 由于t[pos]的含義不能很好確定，因此只能采取笨方法，不斷遞減lowbit(pos)獲得a[1] to a[pos]的前綴和，然后再來求某一區間的和。

int query(int pos) {int sum = 0;while (pos >0) {sum += t[pos];pos -= lowbit(pos);}return sum;
}

適用問題

前綴和數組支持$O(1)$的區間和查詢，但是不支持動態的區間修改

差分數組支持$O(1)$的區間修改，但是不支持動態的單點求值

樹狀數組相當于是一個折中，區間修改和查詢的復雜度為$O(logn)$

例題：

• P3374 【模板】樹狀數組 1：動態區間修改和區間求和。樹狀數組作為前綴和。
• P3368 【模板】樹狀數組 2：動態區間修改和輸出單一數組值。樹狀數組作為差分數組。
• P1908 逆序對：暴力解法的優化。