poj 2352 Stars 线段树(先建后查/边建边查)/树状数组三种方法思路详解,带你深入了解线段树难度⭐⭐⭐★

poj 2352 Stars

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

Hint

This problem has huge input data,use scanf() instead of cin to read data to avoid time limit exceed.
题目大意：
给你n个点代表n个星星，以该点为起点向x，y轴作垂线，会得到一个矩形，这个矩形里面所包含的星星数（不包括它本身）称为该星星的等级（换句话说就是画直接看图，每个点左下角的一个矩形范围内所有的星星数目即为它的等级），要求输出在0~(n-1)等级各有多少个星星。

注意给出的点的顺序很有讲究，是按照y坐标升序给出，如果y坐标相同，则按照x坐标升序给出，题目这样说就相当于减少了这个题目的难度，如果题目没有给出这样的提示，我们也需要这样进行处理。

1.树状数组

树状数组能做的线段树基本上都能做（线段树天下第一！）

这道题用树状数组来做代码比较简练（树状数组是真的简单）

统计x前面比它小的星星的个数。注意的是：给的点的坐标是从0开始的，树状数组下标为0的位置不可用，所以我们需要在输入x坐标时+1。

因为本题给出的数据就是已经按照y从小到大排好序的,也就是说，当前读到一个点的时候，当前点的y坐标肯定比已经读入的大，或者等于。就算是等于的话，也是x坐标比我当前点的x坐标小，所以我们每次只要算x坐标比我们小的就行了 。

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
#define debug(x) cerr<<"# "<<x<<endl
const ll N=32007;
ll ans[N],c[N],n,m;
inline ll lowbit(ll x)
{
    return x&(-x);
}
inline void add(ll i,ll val)
{
    while(i<N)
    {
        c[i]+=val;
        i+=lowbit(i);//i的父节点更新所有父节点
    }
}
inline ll sum(ll i)
{
    ll res=0;
    while(i>0)
    {
        res+=c[i];
        i-=lowbit(i);//i的前驱//寻找所有的子节点+++
    }
    return res;
}
ll x,y;
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld %lld",&x,&y);
        x++;//树状数组必须从1开始
        ans[sum(x)]++;//必须放入之前就++不然会算上自己
        add(x,1);//更新整棵树
    }
    for(ll i=0;i<n;++i)
    {
        printf("%lld\n",ans[i]);
    }
    return 0;
}

2.线段树，先建树后查找

因为数据的独特性，后输入的值不会改变前面的答案，所以也可以先建树，然后再修改查找。

既然y值以升序给出，那问题就简化成了: 给定一个数列a, 求a[1]至a[i-1]共有多少个数在[0, i]之间。(然后统计一下即可)

不难观察到，线段树很适合处理此类问题。（垃圾树状数组，线段树天下第一）

数据不大，直接整个数据范围建树或者输入的时候用max()找到最大值建树可以省空间。

每次添加新的节点，找到x应该所在的那个节点，然后沿着递归之路每到一个节点就 num++ , 直到找到为止。

每次添加之前先询问，询问时求出区间 $[0,x]$[0,x]所跨子区间的 $num$num值之和。

由此算出level, 然后统计即可。

时间复杂度 $O\left(nlogn\right).$O(nlogn).

易错点：

1. 线段树区间从0开始，而不是1.

2. 线段树的数组要开 N 的4倍， $N=32000$N=32000

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
#define debug(x) cerr<<"# "<<x<<endl
const ll N=32007;
struct node
{
    ll left,right,num,lazetag;
};
ll lvl[N+2];
struct segment
{
    node tree[N*4];

    void init()//正常的初始化
    {
        for(int i=1;i<=N*4;++i)
            tree[i].left=tree[i].right=tree[i].num=0;
    }

    void build(ll l,ll r,ll pos)//正常的建树
    {
        tree[pos].left=l;
        tree[pos].right=r;
        if(l==r)return ;//tree[pos]=arr[r];
        ll mid=(l+r)>>1;
        build(l,mid,pos<<1);
        build(mid+1,r,pos<<1|1);
    }
    void addval(ll l,ll r,ll val,ll pos)//正常的修改
    {
        tree[pos].num+=1;
        if(l==r)return ;
        ll mid=(tree[pos].left+tree[pos].right)>>1;
        if(val<=mid)addval(l,mid,val,pos<<1);
        else addval(mid+1,r,val,pos<<1|1);
    }
    ll query(ll l,ll r,ll pos)//正常的查询
    {
        ll mid=(tree[pos].left+tree[pos].right)>>1;
        if(tree[pos].left>=l&&tree[pos].right<=r)return tree[pos].num;
        ll ans=0;
        if(tree[pos*2].right>=l)
            ans+=query(l,r,pos<<1);
        if(tree[pos*2+1].left<=r)
            ans+=query(l,r,pos<<1|1);
        return ans;
    }
};
segment st;
ll a[N];
ll n;
int main()
{
    scanf("%lld",&n);
    st.init();
    st.build(0,N,1);
    for(int i=1;i<=n;++i)
    {
        ll x,y;
        scanf("%lld %lld",&x,&y);
        lvl[st.query(0,x,1)]++;//先查
        st.addval(0,N,x,1);//再改，防止把自己加上
    }
    for(int i=0;i<n;++i)//输出从0到n-1的level
        printf("%lld\n",lvl[i]);
    return 0;
}

3.线段树，边建树边查找

边建树边查找，因为线段树是一维的，然而坐标本来是两维的，这道题之所以能够使用线段树，是因为y坐标按升序给出，这样也就不用考虑
y坐标了，如果是先建树后查找就会出现问题，虽然x坐标大，但是y坐标未必是最大的，这样就会出错，因此必须要边建树边查找，这样就可以保证后面
给出的点不会影响查找结果的正确性。

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
#define debug(x) cerr<<"# "<<x<<endl
const ll N=32007;
ll X[N],tree[N*4];
ll level[15007];
inline void build(ll i,ll l,ll r,ll k)//建树和更新放到一块
{
    if(l==r)
    {
        tree[i]++;
        return ;
    }
    ll mid=(l+r)>>1;
    if(mid>=k)build(i*2,l,mid,k);//普通的线段树是左右子树都建，这棵树是精准定位到k(x[i])。
    else build(i*2+1,mid+1,r,k);//二分精确定位，只有x这一个点会++
    tree[i]=tree[i*2]+tree[i*2+1];//往上更新，
}
inline ll finds(ll i,ll l,ll r,ll x,ll y)
{
    if(l<=x&&r<=y)return tree[i];
    ll mid=(l+r)>>1;
    if(y<=mid)return finds(2*i,l,mid,x,y);
    if(x>mid)return finds(2*i+1,mid+1,r,x,y);
    else return finds(2*i,l,mid,x,mid)+finds(2*i+1,mid+1,r,mid+1,y);
}
ll n,m,maxn,y;
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld %lld",&X[i],&y);
        maxn=max(maxn,X[i]);
    }
    for(int i=1;i<=n;++i)
    {
        build(1,0,maxn,X[i]);//边建树边查找
        level[finds(1,0,maxn,0,X[i])-1]++;//数据比较特殊其实本来应该自己这样排序，后输入的不会影响前面输入的level
    }
    for(int i=0;i<n;++i)
        printf("%lld\n",level[i]);
    return 0;
}

有任何疑问欢迎评论哦虽然我真的很菜