从前缀和数组到树状数组-爱代码爱编程
前缀和
前缀和数组:
初始化:O(n)时间复杂度,顺序扫描原数组即可
查询区间和:O(1)时间复杂度,S[j]-S[i]即为原数组i到j的区间和
单点修改:O(n)时间复杂度,需要修改S[i]~S[n]的所有值
慢,是因为S[i]的值与之前原数组中所有项都有关系
弱化这种关系,即可加快单点修改速度,当然也会丧失部分查询速度,但是这种取舍是值得的。
lowbit函数
定义:lowbit(i)代表i这个数字,二进制表示的最后一位1的位权。
lowbit(x) = x & (-x)
树状数组
改进前缀和:
lowbit(i):代表C[i]代表前lowbit(i)项的和(向前数lowbit项的和)
例如:
lowbit(10) = 2 , C[10] = a[10] + a[9]
lowbit(12) = 4 , C[12] = a[12] + a[11] + a[10] + a[9]
树状数组的基础知识
基本操作:
前缀和查询:
S[i] = S[i-lowbit(i)] + C[i]
例如:
S[7] = S[6] + C[7] = S[4] + C[6] + C[7] = C[4] + C[6] + C[7]
S[12] = S[8] + C[12] = C[8] + C[12]
单点修改:
当修改A[j]位置的值的时候,首先需要更新的显然是C[j]的值,可C[j]之后,应该更新哪个值呢?也就是找到C[j]脑袋上面的区间。
例如:
更新原数组A[5]的值,那么需要更新C[5],C[6],C[8]的值。
Leetcode-1109 例题解析:
//将树状数组建立在查分数组之上
#define lowbit(x) (x & (-x))
class FenwickTree{
public:
FenwickTree(int size):n(size),c(n+1){}
void add(int i,int x){
while(i<=n)c[i]+=x,i+=lowbit(i);
return;
}
int at(int ind){return query(ind)-query(ind-1);}
int query(int x){
int sum = 0;
while(x) sum+=c[x],x-=lowbit(x);
return sum;
}
void output(){
int len = 0;
for(int i=1;i<=n;i++){
len += printf("%5d",i);
}
printf("\n");
for(int i=0;i<len+6;i++){
printf("=");
}
printf("\n");
for(int i=1;i<=n;i++){
printf("%5d",c[i]);
}
printf("\n");
for(int i=1;i<=n;i++){
printf("%5d",query(i)-query(i-1));
}
printf("\n\n\n");
return ;
}
private:
int n;//下标上限
vector<int> c;
};
class Solution {
public:
vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
FenwickTree tree(n);
for(auto x:bookings){
//x[0] -- x[1]+x[2]
tree.add(x[0],x[2]);
tree.add(x[1]+1,-x[2]);
}
vector<int> ret(n);
for(int i=1;i<=n;i++){
ret[i-1] = tree.query(i);
}
return ret;
}
};