2352.txt

pku acm 2352题

树状数组



何为树形数组呢?? 
下图中的C数组就是树状数组,a数组是原数组; 
 
可以发现这些规律: 
C1=a1 
C2=a1+a2 
C3=a3 
C4=a1+a2+a3+a4 
C5=a5 
…… 
C8=a1+a2+a3+a4+a5+a6+a7+a8 
…… 
C2^n=a1+a2+….+a2^n 

对于序列a，我们设一个数组C定义C[t] = a[t – 2^k + 1] + … + a[t]，k为t在二进制下末尾0的个数。 
K的计算可以这样: 
2^k=t and (t xor (t-1)) 
以6为例 
               (6)10=(0110)2 
xor    6-1=(5)10=(0101)2 
                        (0011)2 
and          (6)10=(0110)2 
                        (0010)2 

所以问题变的很简单,重要写几个函数就可以了; 
求2^k的函数代码如下: 

int Lowbit(int t) 
{ 
    return t & ( t ^ ( t - 1 ) ); 
} 
 


求1 -- end和的函数代码如下: 

int Sum(int end) 
{ 
    int sum = 0; 
    while(end > 0) 
    { 
        sum += in[end]; 
        end -= Lowbit(end); 
    } 
    return sum; 
} 
 


对某位进行操作函数如下(以加法为例) 

void plus(int pos , int num) 
{ 
    while(pos <= n) 
    { 
          in[pos] += num; 
          pos += Lowbit(pos); 
    } 
} 
 


有了这三个函数整个树形数组也就基本构建成功啦!! 
对于刚才的一题,每次修改与询问都是对C数组做处理.空间复杂度有3N降为N,时间效率也有所提高.编程复杂度更是降了不少. 

代码如下:
#include<stdio.h>
typedef struct item
{
 int x,y;
}Co;
Co date[15003];
int result[15003];
void solve(int n)
{
 int i,j,count=0;
 memset(result,0,sizeof(result));
 for(i=n-1;i>=0;i--)
 {
  count=0;
  for(j=i-1;j>=0;j--)
  {
   if(date[j].x<=date[i].x)
   {
    count++;
   }
  }
  result[count]++;
 }
}
main()
{
 int i,n;
 scanf("%d",&n);
 for(i=0;i<n;i++)
 {
  scanf("%d%d",&date[i].x,&date[i].y);
 }
 solve(n);
 for(i=0;i<n;i++)
 {
  printf("%d\n",result[i]);
 }
}