樹狀數組是一種代碼量小，維護區間的數據結構
他可以實現：
1.區間修改，單點查詢
2.單點修改，區間查詢
當然，二者不可兼得，大人全都要的話，請選擇線段樹
前置知識：
lowbit(x)操作：
獲取x二進制的最后一位1以及其后面的0所組成的數
比如x等于6時，其二進制為110,那么lowbit(6)就等于2，其二進制為10
這里有：
lowbit(x)=x&(-x)
樹狀數組的特性：
對于樹狀數組tr[N]而言
tr[x+lowbit(x)]是tr[x]的父親
對于區間[1,x]而言
其區間和等于
操作：
設原數組為a[N],大小為n,樹狀數組為tr[N],
1.單點修改，區間查詢：
假設我們要對a[x]的權值進行修改，那么我們對tr[x]進行修改，然后不斷pushup他的父結點，也就是tr[x+lowbit(x)]就可以了，直到pushup到tr[n]
如果我們要對區間[l,r]進行查詢，我們只要求出區間[1,l-1],[1,r]，然后利用前綴和就可以求出區間[l,r]的和了
實現代碼如下：
int lowbit(int x){return x & (-x);
}//單點修改
void pointAdd(int x,int k){for (int i = x; i <= n;i+=lowbit(i)){tr[i] += k;}
}//查詢區間[l,r]
int queryLine(int l,int r){int sum = 0;for (int i = r; i;i-=lowbit(i)){sum += tr[i];}for (int i = l - 1; i;i-=lowbit(i)){sum -= tr[i];}return sum;
}
2.區間修改，單點查詢
其實本質上還是利用樹狀數組單點修改的方便性
這里我們構造原數組的差分數組d，然后用樹狀數組來維護數組d
當我們需要對原數組的區間[l,r]進行加權值k的修改時，只需要對差分數組d[l]和d[r+1]進行單點修改就可以了
當我們需要對原數組的a[x]進行查詢時，只要求出d數組[1,x]的區間和就可以了
實現代碼如下：
//初始化差分數組以及樹狀數組
void init(){for (int i = 1; i <= n;i++){d[i] = a[i] - a[i - 1];for (int j = i; j <= n;j+=lowbit(j)){tr[j] += d[i];}}
}//區間修改
void change(int l,int r,int k){for (int i = r + 1; i<=n;i+=lowbit(i)){tr[i] -= k;}for (int i = l;i<=n;i+=lowbit(i)){tr[i] += k;}
}//單點查詢
int query(int x){int sum = 0;for (int i = x; i;i-=lowbit(i)){sum += tr[i];}return sum;
}
)
