树状数组专题(一)POJ2352

#include<stdio.h>

#include<stdlib.h>

#include<iostream>

#include<math.h>

#include<string.h>

using namespace std;

const int maxn = 32101;

int tree[maxn];

int Lowbit(int x)

{

    return x&(-x);

}

void Updata(int x)

{

    for(int i = x ; i <= maxn; i += Lowbit(i))

    {

        tree[i]++;

    }

}

int Getsum(int x)

{

    int sum = 0 ;

    while(x > 0)

    {

        sum = sum + tree[x];

        if(!Lowbit(x))x--;

        else x = x - Lowbit(x);

    }

    return sum;

}

int ans[maxn];

int main()

{

    int x,y,n;

    while(scanf("%d",&n) != EOF)

    {

        memset(tree,0,sizeof(tree));

        memset(ans,0,sizeof(ans));

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

        {

            scanf("%d%d",&x,&y);

            x++;//由于坐标是(0, )的情况下.Lowbit返回的是0.所以会TLE

            ans[Getsum(x)]++;

            Updata(x);

        }

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

        printf("%d\n",ans[i]);

    }

}

//总结:这是做的第一个树状数组的题目.其实基本的思想就是当我的X出现一个新的值的时候.比如8,那么,从8-->maxn

//的值.我都要加1.全部处理好了之后就可以有结果了...当然..这个是爆搜的处理方法..

//通过这个爆搜来比较,加深了一点对树状数组的体会..它在记录的时候并不是从8-->maxn逐个都处理..而是通

//过Lowbit的累加来处理..这样形成了一个把n->logn的转变,最开始理解的时候会误解成那么我8到下一位就是16..

//这样的话.我后面的9,10,11,12,13,14,15都没有被处理.能够保证正确么,.?.能,因为在提取值的时候,即Getsum

//函数里面的时候..返回值的处理方式也是类似的..比如我要算9的..那么sum = tree[9]+tree[8].而tree[9]只包含

//拥有9的..不记录1-->8的..所以结果是正确的..同样..要算10的..那么sum=tree[10]+tree[8]..而tree[10]=9+10的;

//所以能够保证结果的正确性.