Tags

,

树状数组(Binary Indexed Trees，二分索引树)，现多用于高效计算数列的前缀和。它可以以O(log n)的时间得到前缀和，并同样以O(log n)对某项加一个常数。

在需要大量计算数列前缀和的时候，我们希望有效利用之前计算过的结果。即，将数列[1-n]的和分成多个部分，每个部分的值是已知的。比如，长度为7的前缀和，由于 7 = 2^2 + 2^1 + 2^0，如果我们得到了2^2对应的和(a1+a2+a3+a4),2^1对应的和(a5+a6),以及a7，直接相加即可。显然，这个求和的时间复杂度为O(log n)。

于是，我们需要找一个数组C，它保存了2^n个元素和的信息。编号为奇数的对应当前数，C2、C4、C8…分别代表前2、4、8…个元素的和是显而易见的。对于C6，由于6=4+2，可以表示成C6=a5+a6，

计算[1-6]的和只需计算C6+C4。依次类推。我们定义这样一个函数lowbit(x) = x & (-x)，它实现了取出一个正整数的二进制表示的最后一个1对应的数，如 lowbit(111100) = 100。那么，容易得出Cn代表的和对应的区间长度=lowbit(n)。不断令n = n – lowbit(n)，就可以找到所有参与计算的Cn。

对于更新操作，如a5的更新，就需要改变C5、C6、C8的值。相当于是上述过程的逆过程。

Star这道题由于y、x是递增给出的，第y层增加减少星星数目对y-1层毫无影响。每增加一颗星星(x,y),只需要统计[1-x]区间星星的数目，就能得到它的level值，另外别忘了更新x之后的数组。这道题是标准的树状数组。用的递归实现（其实用循环看上去更简单一点）。下面是代码：

#include <stdio.h>

#define MAXN 32001
int bit[MAXN]; //Binary Indexed Tree

int lowbit(int x)
{
    return x&(-x);
}

int sum(int n)
{
    if (n < 1)   return 0;
    return bit[n] + sum(n - lowbit(n));
}

void increase(int n)
{
    if (n > MAXN)
        return;
    bit[n] ++;
    increase(n + lowbit(n));
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n;
    scanf("%d",&n);

    int level[MAXN] = {0};
    int x,y;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d %d",&x,&y);
        int s = sum(x + 1);
        level[s] ++;
        increase(x + 1);
    }
    for (int i = 0; i < n; i++)
    {
        printf("%dn",level[i]);
    }
    return 0;
}