树状数组入门+例题Ping Pong

树状数组入门

对于给定的包含n个元素的数组A，查询（L，R）间Ai的和，我们可以暴力查找，每一次查询将花费O(n)的代价，效率太低。我们会想到前缀和的方法，做预处理求出sum[i] (a1+a2+…+ai)，让查询的复杂度降低为O(1)。但是，如果我们要对单点进行修改，我们将花费O(n)的代价。那么怎么让我们的查询和更新的效率都变得更高呢（相对于暴力查找）？树状数组可以将查询和更新的复杂度都降为O(logn)。

在介绍树状数组前，我们需要先知道lowbit。对于正整数x，我们定义lowbit(x)为x的二进制表达式中最右边的1所对应的值。在程序实现中lowbit(x)=x&-x，读者可以自行验证，这里将x与-x化为二进制补码按位取与。
树状数组入门+例题Ping Pong

如上图（来源于蓝书195面，记作图1），我们可以知道每一层节点的lowbit相同，而且lowbit越大，越靠近根。对于节点I,如果它是左子节点，那么它的父节点的编号是i+lowbit(i);如果它是右子节点，那么它的父节点的编号是i-lowbit(i)。我们构造一个辅助数组C，来存储一个部分前缀和，其中ci=ai-lowbit(i)+1+ai-lowbit(i)+2+…+ai。从图上看就是对应的白条所包含的元素的和，如果lowbit(i)=1，那么就是该元素本身。这样，我们就求得了各个部分的前缀和，并且这种分法运用了二分的思想，让查询和更改的复杂度都降到了log级别。

如果我们要求i的前缀和，只需要从i开始往左走（x=x-lowbit(x),x为当前走到的点的编号），将c[x]的值加起来即可，读者可以自行验证。如果我们需要更新某个点的值，只需要更改当前点的值后往右走，沿途更改c[y]的值即可（y=y+lowbit(y),y为当前走到的点的编号）。

下面给出求和操作的代码：

int sum(int x){
  int ret=0;
  while(x>0){
     ret+=c[x];
     x-=lowbit(x);
  }
  return ret;
}

下面给出更新操作的代码：

void add(int x,int d){
  while(x<=100005){
     c[x]+=d;
     x+=lowbit(x); 
  }
}

最后给出一道入门例题UVALive 4329(Ping pong)及代码：
树状数组入门+例题Ping Pong

/* 
作者:acmlog
UVALive Ping pong
*/

#include<iostream>

#include<string.h>

using namespace std;

int c[100005];

int t;

int n;

int a[100005];

int s1[100005];

int s2[100005];

int lowbit(int x){

  return x&-x;

}

int sum(int x){

  int ret=0;

  while(x>0){

     ret+=c[x];

     x-=lowbit(x);

  }

  return ret;

} 

void add(int x,int d){

  while(x<=100005){

     c[x]+=d;

     x+=lowbit(x); 

  }

}

int main(){

  cin>>t;

  while(t--){

     cin>>n;

     for(int i=1;i<=n;i++)

     cin>>a[i];

     memset(c,0,sizeof(c));

     for(int i=1;i<=n;i++){

        add(a[i],1);

        s1[i]=sum(a[i]-1);

     }//s1数组用于求i之前比i小的元素个数 

     memset(c,0,sizeof(c));

     for(int i=n;i>=1;i--){

        add(a[i],1);

        s2[i]=sum(a[i]-1);

     }//s2数组用于求i之前比i大的元素个数 

     long long ans=0;

     for(int i=2;i<=n;i++){

        ans+=s1[i]*(n-i-s2[i])+(i-s1[i]-1)*s2[i];

     }

     cout<<ans<<endl;

  }

  return 0;

}

本文仅用于入门，更多应用读者可以自行查阅其他文章。

树状数组入门+例题Ping Pong

树状数组入门

相关推荐