见微知著----POJ2352（树状数组 或 线段树）

POJ2352 Stars

Description
Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are not higher and not to the right of the given star. Astronomers want to know the distribution of the levels of the stars.

For example, look at the map shown on the figure above. Level of the star number 5 is equal to 3 (it`s formed by three stars with a numbers 1, 2 and 4). And the levels of the stars numbered by 2 and 4 are 1. At this map there are only one star of the level 0, two stars of the level 1, one star of the level 2, and one star of the level 3.

You are to write a program that will count the amounts of the stars of each level on a given map.
Input
The first line of the input file contains a number of stars N (1<=N<=15000). The following N lines describe coordinates of stars (two integers X and Y per line separated by a space, 0<=X,Y<=32000). There can be only one star at one point of the plane. Stars are listed in ascending order of Y coordinate. Stars with equal Y coordinates are listed in ascending order of X coordinate.
Output
The output should contain N lines, one number per line. The first line contains amount of stars of the level 0, the second does amount of stars of the level 1 and so on, the last line contains amount of stars of the level N-1.
Sample Input
5
1 1
5 1
7 1
3 3
5 5
Sample Output
1
2
1
1
0

题目简介：
有若干星星，给出每个星星的二维坐标，定义每个星星的级别为横纵坐标均不超过自己的星星个数，问级别为0~N-1的星星分别有多少个。
题目解析：
由于星星的坐标按照横纵坐标递增排序，所以对于第i颗星星，它的level就是之前出现过的星星中，横坐标小于等于该星星的数。相当于我们需要求出0-x线段上星星的数量。

介绍树状数组的概念：
树状数组通过一个节点表示一个线段。对于原数据a[ ],树状数组c[ ]表示的线段是c[n] = a[n-2^k+1]+…+a[n],其中k是n在二进制下末尾0的个数，比如n = 8(1000)，那么对应的k为3。这个c[ ]数组就是树状数组。

如何计算2^k呢？2^k = x&(x^(x-1))，相当于x&(-x)

int lowbit(int x)   //lowbit函数
{
    return x&(-x);
}

树状数组需要的操作如下：
1、查询获得前i个元素和
2、更新a[i]的数据

查询操作：

上面的图片介绍了查询线段数组的过程。把0作为根节点，若y是x的父亲节点，那么存在y = x – x&(-x)；从这棵树的自下而上来看，从而逐一寻找到经过的元素。比如当i = 11时，11(1011) = 8(1000)+2(10)+1(1),逐个去除2^k元素，可以得知其经过元素11,10,8,即sum(11) = c[11]+c[10]+c[8]。所以如果想求前11个元素的和，只需要将c[11],c[10],c[8]的元素相加就可以了。

查询操作代码如下：

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

更新操作：
更新操作需要我们经过全部包括a[ ]元素的节点，由于线段树的特性，可能这个x在若干个c[]里都存在，所以要更新的节点不只有一个。若y是x的父亲节点，则y = x + x&(-x)。比如当x = 5(101)的时候，y = x + x&(-x) = (101)2+(1)2=(110)2=6,同理,6的父亲节点是8，8的父亲节点是16，以此类推，从而使得树状数组得到更新。

更新操作的代码如下：

void update(int pos,int num)
{
    while(pos <= N)
    {
        c[pos] += num;
        pos += lowbit(pos);
    }
}

树状数组比起线段树，它比线段树更加节省空间，编程复杂性比线段树低，但适用范围比线段树小；比如求一段数字中最大或者最小的数字，就不能使用树状数组了。
一般来说，能用树状数组解决的问题用线段树都可以解决；以下是本题的线段树及树状数组的代码表示。

树状数组代码：

#include <iostream>
#include <cstdio>
using namespace std;
int n;
int levels[32001]; //保存等级
int c[32001]; //树状数组
int lowbit(int x)
{
    return x&(-x);
}
int sum(int x)  //查询1到x区间的和
{
    int s = 0;
    while(x>0)
    {
        s += c[x];
        x -= lowbit(x);
    }
    return s;
}
void update(int pos)    //更新树状数组
{
    while(pos <= 32001)
    {
        c[pos]++;
        pos += lowbit(pos);
    }
}
int main()
{
    scanf("%d",&n);
    int x, y;
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d",&x,&y);
        levels[sum(x+1)]++; //避免出现x=0的情况 所有x右移一位
        update(x+1);
    }
    for(int i=0; i<n; i++)
    {
        printf("%d\n",levels[i]);
    }
    return 0;
}

线段树代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAX 32001
using namespace std;
int levels[2*MAX];
int c[2*MAX];
struct segment
{
    int left;
    int right;
    int kind;
};
segment Tree[4*MAX];
void build(int root,int left,int right)
{
    Tree[root].left = left;
    Tree[root].right = right;
    Tree[root].kind = 0;
    if(left == right) return;
    build(root*2,left,(left+right)/2);
    build(root*2+1,(left+right)/2+1,right);
}

void query(int root,int key,int pos)
{
    Tree[root].kind++;
    if(Tree[root].left == Tree[root].right)
        levels[pos] += Tree[root].kind-1;
    else if(key <= (Tree[root].left+Tree[root].right)/2)
        query(root*2,key,pos);
    else
    {
        levels[pos] += Tree[root*2].kind;
        query(root*2+1,key,pos);
    }
}
int main()
{
    int n,min = MAX,max = 0,i,pos;
    int x[MAX],y;
    memset(levels,0,sizeof(levels));
    memset(c,0,sizeof(c));
    scanf("%d",&n);
    for(i = 1; i<=n; i++)
    {
        scanf("%d%d",&x[i],&y);
        if(x[i] < min) min = x[i];
        if(x[i] > max) max =x[i];
    }
    for(i = 1; i<=n; i++)
        x[i] -= min;
    build(1,0,max-min);
    for(pos=1; pos<=n; pos++)
    {
        query(1,x[pos],pos);
    }
    for(i = 1; i<=n; i++)
    {
        c[levels[i]]++;
    }
    for( i=0; i<n; i++)
        printf("%d\n",c[i]);
    return 0;
}