数据结构————树状数组

原数组--->前缀和------>范围和

原数组更改数组元素在求和效率较低，引入树状数组

假设原数组A【】 树状数组C【】

树状数组 的三种操作：

1.lowbit（） 子叶数(二进制最低位的1代表多少）

 

代码实现：

 int lowbit(int n)
{
   return x&(-x);
}

 

 

求：lowbit（x） returnx&(-x)

2.

update（）// A[i]+k       假设A【i】是原数组C[i]为树状数组，改变A【i】个更新C[i]

   update（i，k） ；

  c[i]=c[i]+k;//首先更新从c【i】本身，然后更新它的父节点

   i=i+lowbit(i);//更新c[i]的父节点
   i<=n；//下一步 循环update（）更新所有的父节点，直到满足截止条件i<=n

代码实现：

/*树状数组支持单点操作，对某个数A【x】加上y，同时正确维护序列的前缀和*/
void update(int x,int y)
{
   for(;x<=N;x+=x&-x)
     c[x]+y;
}

3.sum()利用树状数组求原数组的前缀和

sum（i）;//表示从A【1】一直加到A[i]
ans=c[i]+ans;
i=i-lowbit(i);//循环
i>0;//循环截止的条件

如：求区间【l~r】的和

sum（k）-sum(l-1)；

代码实现：

树状数组支持查询前缀和，即序列A~x个数的和

int sum(int x)
{
  int ans;
  for(;x-=x&-x) ans-=c[x];
  return ans;
}