理论上是2n-1的空间，但是你递归建立的时候当前节点为r,那么左右孩子分别是2*r,2*r+1,此时编译器并不知道递归已结束，因为你的结束条件是在递归之前的，所以编译器会认为下标访问出错，也就是空间开小了，应该再开大2倍。有时候可能你发现开2，3倍的空间也可以AC，那只是因为测试数据并没有那么大。

这种数据结构主要应用在计算几何和地理信息系统中

树状数组相比线段树的优势：空间复杂度略低，编程复杂度低，容易扩展到多维情况。劣势：适用范围小，对可以进行的运算也有限制，比如每次要查询的是一个区间的最小值，似乎就没有很好的解决办法。

题意快速理解：给出n个平面二维坐标，对于每个坐标，如果这个坐标跟(0,0)形成的矩形内包含的点数为 k （包含边界，但不包含坐标本身），那么这个坐标就是 level k。输出level 0 - n-1的点数分别是多少。

用树状数组解决时，对于已经读入的坐标，看做是一个点，存入线段树内。

对于X，统计结果时，统计[0,x]内共有多少个点，即为它的等级

#include <stdio.h>

#include <string.h>

#include <conio.h>

#define N 15000

#define M 32000

struct t

{

    int l;

    int r;

    int w;

}tree[M * 3];//坐标范围是32000,3m 保证够用

void maketree(int s, int t, int n)

{

    tree[n].l = s;

    tree[n].r = t;

    tree[n].w = 0;

    if(t == s)

        return;

///////////////////////////////////////////////////////////////////////////////////////

N从1开始，根节点表示从（0，MAX）共有多少节点

///////////////////////////////////////////////////////////////////////////////////////

    int mid = (tree[n].l + tree[n].r) / 2;

    maketree(s, mid, n * 2);//静态数组

    maketree(mid + 1, t, n * 2 + 1);

}

/*在[s,t]范围内共有多少节点,s初始为0，由于y递增，不用考虑后面的节点和自己，只需要考虑前面的已经存在的。*/

int find(int s, int t, int n)

{

    if(tree[n].l == s && tree[n].r == t)

        return tree[n].w;

    else

    {

        int sum = 0;

        int mid = (tree[n].l + tree[n].r ) >> 1;

/*n=1从根节点开始找，假设s=0,.t=5，如果能恰好找到[0,5]区间的值，那么最好，【0,5】区间的w权值即为所求，如果不能则是分散在几个区间，比如求[0,7]，在下面的三个if中，只能满足第三个条件，于是把[0,5],[6,7]两个区间权值求和*/

        if(s > =mid+1 )//这里是s>=，因为分区域按照[s,mid],[mid+1,t]分的所求区域在当前父节点的右边区域

            sum += find(s, t, n * 2 +1);

        else if(t <= mid)//所求区域在当前节点的左边区域

            sum += find(s, t, n * 2);

        else

            sum += find(s, mid, n*2) + find(mid+1, t, n*2+1);

//[s,mid]段在左边找，[mid+1,t]段在右边找

        return sum;

    }

}

/*在x位置处又多了一个节点，N从1开始，因为无论如何肯定属于根节点范围[0,max]，然后再逐渐在更小的区域上，增加各个区域的点数目，比如节点2 ，即属于[0,10],也属于[0,5],[0,2],[2,2]*/

void insert(int x, int n)

{

    tree[n].w++;

    if(tree[n].l == tree[n].r && tree[n].r == x)

        return;

    int mid = (tree[n].l + tree[n].r ) >> 1;

    if(x <= mid)

        insert(x, n * 2);

    else insert(x, n * 2 + 1);

}

int main()

{

    int i;

    int n, max;

    int a[N], b, ans[M];

    freopen("in.txt", "r", stdin);

    scanf("%d", &n);

    max = 0;

    for(i=0; i<n; i++)

    {

        scanf("%d%d", &a[i], &b);

        max = max < a[i] ? a[i] : max;

    }

    maketree(0, max, 1);

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

    for(i=0; i<n; i++)

    {    

        ans[find(0, a[i], 1)]++;

        insert(a[i], 1);

    }

    for(i=0; i<n; i++)

    {

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

    }

    getch();

    return 0;

}

TreeSegment2352