树状数组基础知识

lowbit:

lowbit(x)=x&(-x)

树状数组：

树状数组的功能：

数组

在O(1)的时间复杂度实现单点加：

在O(lng n)的时间复杂度实现查询前缀和：

树状数组的定义：

查询前x项的和操作：

ll query(int x){ll s=0;for( ; x; x-=x&(-x)){s+=c[x];}return s;
}

单点加操作：

//原数组长度为n
void modify(int x,ll s){for(;x<=n;x+=x&(-x)){c[x]+=s;}//如果需要别忘了把元素组对应的一位也进行变换
}

构造一个树状数组：

//原数组长度为n
scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",a+i);modify(i,a[i]);}

在输入元素的每一位时对应的在树状数组的位置加上该值。