樹狀數(shù)組（Binary Index Tree, BIT）是用用數(shù)組來模擬樹形結(jié)構(gòu)躺孝。最簡單的樹狀數(shù)組支持兩種操作，時間復(fù)雜度均為：
- 單點(diǎn)修改：更改數(shù)組中一個元素的值
- 區(qū)間查詢：查詢一個區(qū)間內(nèi)所有元素的和
樹狀數(shù)組-01.png
數(shù)組的構(gòu)建：
int[] tree = new int[len];
求前n項(xiàng)和：
求和時需要如此計(jì)算SUM_i=C[i]+C[i-2^(k1)]+C[i-2^(k1)-2^(k2)]+···，那么2^k應(yīng)該通過i&(-i)凄敢。求和就是不斷地去掉二進(jìn)制數(shù)最右邊的一個1的過程迅细。
public int query(int n) {
int res = 0;
for (int i = n; i > 0; i -= lowbit(i)) res += tree[i];
}
以計(jì)算前7項(xiàng)的和為例衅谷，最終結(jié)果會依次將C[7]、C[6]膀斋、C[4]求和梭伐。
為什么使用
i&(-i)替代2^k呢？這里利用的負(fù)數(shù)的存儲特性仰担，負(fù)數(shù)是以補(bǔ)碼存儲的糊识，對于整數(shù)運(yùn)算
x&(-x)有：
- 當(dāng)
x為0時，0&0=0- 當(dāng)
x為奇數(shù)時摔蓝，最后一個比特位為1赂苗，取反加1沒有進(jìn)位，故x和-x除最后一位外前面的位正好相反贮尉，按位與結(jié)果為0拌滋。結(jié)果為1。- 當(dāng)
x為偶數(shù)猜谚，且為2的m次方時败砂，x的二進(jìn)制表示中只有一位是1（從右往左的第m+1位）赌渣，其右邊有m位0，故x取反加1后昌犹，從右到左第有m個0坚芜，第m+1位及其左邊全是1。這樣斜姥，x&(-x)得到的就是x鸿竖。- 當(dāng)
x為偶數(shù)，卻不為2的m次方的形式時疾渴，可以寫作x=y*(2^k)千贯，y的最低位為1，x就是一個奇數(shù)左移k位來表示搞坝。這時搔谴，x的二進(jìn)制表示最右邊有k個0，從右往左第k+1位為1桩撮。當(dāng)對x取反時敦第，最右邊的k位0變成1，第k+1位變?yōu)?code>0店量；再加1芜果，最右邊的k位就又變成了0，第k+1位因?yàn)檫M(jìn)位的關(guān)系變成了1融师。左邊的位因?yàn)闆]有進(jìn)位右钾，正好和x原來對應(yīng)的位上的值相反。二者按位與旱爆，得到：第k+1位上為1舀射，左邊右邊都為0。結(jié)果為2^k怀伦。總結(jié)一下：
x&(-x)脆烟，當(dāng)x為0時結(jié)果為0；x為奇數(shù)時房待，結(jié)果為1邢羔；x為偶數(shù)時，結(jié)果為x中2的最大次方的因子桑孩。public int lowbit(int x) { return x & -x; }
區(qū)間求和：
public int query(int a, int b) {
return query(b) - query(a - 1);
}
單點(diǎn)修改：
public void update(int p, int v) {
for (int i = p; i < len; i += lowbit(i)) tree[i] += v;
}
下面針對775. 全局倒置與局部倒置問題使用樹狀數(shù)組進(jìn)行解決：
class Solution {
public boolean isIdealPermutation(int[] nums) {
int len = nums.length;
int l = 0, g = 0;
// local
for (int i = 1; i < len; i++) {
if (nums[i - 1] > nums[i]) {
l++;
}
}
// global
int[] tree = new int[len + 1];
for (int i = 1; i <= len; i++) {
update(tree, nums[i - 1] + 1, 1);
g += i - query(tree, nums[i - 1] + 1);
}
return l == g;
}
public int lowbit(int x) {
return x & -x;
}
public void update(int[] tree, int p, int v) {
for (int i = p; i < tree.length; i += lowbit(i)) {
tree[i] += v;
}
}
public int query(int[] tree, int n) {
int ans = 0;
for (int i = n; i > 0; i -= lowbit(i)) {
ans += tree[i];
}
return ans;
}
}
參考文獻(xiàn)：
