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
个气球排成一排，从左到右依次编号为1,2,3....N.每次给定2个整数a b(a <=
b),lele便为骑上他的“小飞鸽"牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜
色了，你能帮他算出每个气球被涂过几次颜色吗？
当N = 0，输入结束。
设想我们有这样一个问题：给定一个序列，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]维护的值是正确的。
先来个图吧，这样看得明白。
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 > )
{
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 > )
{
sum += c[pos];
pos -= LowBit(pos);
}
return ;
} int main()
{
int a,b,i;
while(~scanf("%d",&n) && n)
{
memset(c,,sizeof(c));
for(i = ;i <= n;i ++)
{
scanf("%d%d",&a,&b);
update(a,);
update(b+,-);
}
for(i = ;i < n;i ++)
{
sum = ;
Get_Result(i);
printf("%d ",sum);
}
sum = ;
Get_Result(i);
printf("%d\n",sum);
}
return ;
}