Color the ball----HDOJ1556

Color the ball

Time Limit: 9000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6614    Accepted Submission(s): 3470

Problem Description

N 个气球排成一排，从左到右依次编号为1,2,3....N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽"牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜 色了，你能帮他算出每个气球被涂过几次颜色吗？

 

Input

每个测试实例第一行为一个整数N,(N <= 100000).接下来的N行，每行包括2个整数a b(1 <= a <= b <= N)。
当N = 0，输入结束。

 

Output

每个测试实例输出一行，包括N个整数，第I个数代表第I个气球总共被涂色的次数。

 

Sample Input

3

1 1

2 2

3 3

3

1 1

1 2

1 3

0

 

Sample Output

1 1 1

3 2 1

 

Author

8600

思路：之前把这题A了，用线段树做的，现在学学树状数组，也不知道 Peter M. Fenwick 当时是怎么想到的，太神奇了，我花了一整天全在研究他的思路，到最后还是没什么进展，不知怎么想的，这就是大神吧。

 

它与线段树不同，线段树是平衡二叉树，对于一个区间很容易从直观上就可以将它划分，[a , b]的子区间（子树）为[a,(a+b)/2]和[(a+b)/2+1,b],很容易就看出来，而对于树状数组区间的划分则不是那样的，很难直接观察得到。那么到底什么是树状数组，下面讲讲我的理解，也算是花了一整天的总结吧，可能不全对。

 

设想我们有这样一个问题：给定一个序列，A1,A2,A3........An,现在需要频繁的查询区间（i，j）里面所有元素的和，而且这个序列中的元素是变化的。当然我们可以用最简单的暴力法，一个个加呗，这样时间复杂度为O（n），插入数据时间复杂度是O（1）的，更新是O（m），这样一来总的时间复杂度会是O（n×m），数据一旦变大，效率太低，此时就要用树状数组，也叫作二叉搜索树（Binary Indexed Trees）BIT。

它基于这样一个定义：令数组C[i] = A[i-2^k+1]+...+A[i],这样以来C[i]表示的就是区间（i-2^k+1,i)的和，这里k表示的是：i对应的二进制数末尾连续0的个数，比如8(10) = 1000(2)，那么k = 3;它所维护的区间是不是很“晦涩”，不知道他是怎么想得，据说Peter M. Fenwick的这样定义的思路来源于二进制思想。我个人认为这是整个树状数组最有价值的部分，也是最值得研究的部分。

1,基于这样一个定义我们的问题来了，对于确定的i，如何计算k的值？换句话说我们要知道2^k的值，再换句话说就是计算二进制位中最右边那个1的位权，不然一切都不用谈了，没意义。而且要高效，其实可以利用C语言位运算来做（用的很巧妙）：

我们可以这样表示一个二进制数：a1b，这里b都是0（0的个数可以是0），a任意，但必须保证1是最右边的那个1,例如 14（10） = 1100（2），那么a=1,b=00,

那么-a1b在计算机里是以补码表示的,即反码加1,我把它记为(a-)0(b-)+1，所以(b-)全为1了，所以(a-)0(b-)+1 = (a-)0(1...1)+1 = (a-)1(0...0), 它再与a1b按为与运算，a1b & (a-)1(0...0) = (0...0)1(0...0)，这样就得到了2^k的值了，很神奇！

写个函数就是：

int LowBit(int t)
{
    return t & (-t);
}

我们就把第一个问题解决了！

这个函数的功能就是寻找当前节点的父节点或者子节点！！！

2,那么我们如何来计算C[i]的值？就是说我们插入数据A[j]的时候如何来更新C[i]？我们不光要更新C[i],而且还要更新与A[j]有关的其他的C[k1]...C[kn],这样才能保证C[i]维护的值是正确的。

先来个图吧，这样看得明白。

例如我们修改A4的值那么C[4],C[8]...,直到n，都得更新，想想为什么？因为A4被C[4]，C[8]...,覆盖！记住一点：某个数被修改，与他相关的区间都得受到牵连，这就是为什么暴力法慢的原因，而树状数组使得受到牵连的区间（即相关的父节点）不会多于LogN（我认为这得归功于那个牛逼的定义），想想为什么！更新函数可以这么写：

void update(int pos,int val)
{
    while(pos <= n)
    {
        c[pos] += val;
        pos += LowBit(pos);
    }
    return ;
}

3,如何得到某个区间（i，j）的和呢？

我们高中就学过sum(i) = A1+A2+A3+...+Ai;

　　　　　　　sum(j) = A1+A2+A3+...+Aj;

那么sum（i->j）= sum(j)-sum(i);

现在问题又来了，怎么知道sum（n）的值的？

我们把1。。。n所包含的子区间的和加一起就可以了，现在关键是如何找区间了，比如给你13,让你求sum（13），怎么找13的子区间？这还得根据LowBit（）函数的计算过程来逆退，刚才不是update函数是加得到的父区间，现在逆过来就减！函数如下：

void Get_Result(int pos)
{
    while(pos > 0)
    {
        sum += c[pos];
        pos -= LowBit(pos);
    }
    return ;
}

三个函数都很简洁，代码比较简单，但思想绝不简单！特别是那个定义！

对于数状数组我今天就理解这么多，以得还的进一步理解。

AC代码：

#include<stdio.h>
#include<string.h>
#define MAX 100005
int c[MAX];
int sum,n;
int LowBit(int t)
{
    return t & (-t);
}

void update(int pos,int val)
{
    while(pos <= n)
    {
        c[pos] += val;
        pos += LowBit(pos);
    }
    return ;
}

void Get_Result(int pos)
{
    while(pos > 0)
    {
        sum += c[pos];
        pos -= LowBit(pos);
    }
    return ;
}

int main()
{
    int a,b,i;
    while(~scanf("%d",&n) && n)
    {
        memset(c,0,sizeof(c));
        for(i = 1;i <= n;i ++)
        {
            scanf("%d%d",&a,&b);
            update(a,1);
            update(b+1,-1);
        }
        for(i = 1;i < n;i ++)
        {
            sum = 0;
            Get_Result(i);
            printf("%d ",sum);
        }
        sum = 0;
        Get_Result(i);
        printf("%d
",sum);
    }
    return 0;
}