HDU 1556 Color the ball （一维树状数组，区间更新，单点查询）

中文题，题意就不说了

一开始接触树状数组时，只知道“单点更新，区间求和”的功能，没想到还有“区间更新，单点查询”的作用。

树状数组有两种用途（以一维树状数组举例）：
1.单点更新，区间查询（即求和）
单点更新时，是往树根（即c[n]）拓展
而区间查询时，是往叶子节点（即c[1]）拓展
2.区间更新，单点查询
区间更新时，是往叶子节点（即c[1]）拓展
单点查询时，往树根（即c[n]）拓展

这两个操作只不过是在update()和sum()方法中的+和-替换一下而已。

思路：

一维树状数组
区间更新，单点查询
区间更新时，是往叶子节点（即c[1]）拓展
单点查询时，往树根（即c[n]）拓展

对于区间[a,b]，我们只要先更新区间[1,b]++,再更新区间[1,a-1]--。
查询时，只要直接向树根拓展，求和即可

下面解释一下“区间更新时，是往叶子节点（即c[1]）拓展” 和 “单点查询时，往树根（即c[n]）拓展” 的原因

举例说明吧：
c[1]=a[1];
c[2]=a[1]+a[2];
c[3]=a[3];
c[4]=a[1]+a[2]+a[3]+a[4];
c[5]=a[5];
c[6]=a[5]+a[6];
c[7]=a[7];
c[8]=a[1]+...+a[8];

假如我要更新区间[3,7]，那么我首先更新[1,7]，即该区间+1；再更新[1,2]，该区间-1：
由于更新时往叶子节点拓展的，所以更新[1,7]时：c[7]++,c[6]++,c[4]++。
可以发现，这三个正好包含了a[1]~a[7]一次，相当于a[1]~a[7]都更新一遍
而更新[1,2]时：c[2]--，包含了a[1]，a[2]。

那么当我查询某一值a[i]，由于是往根节点拓展，所以每个包含a[i]的c[j]都会遇到一次，即之前凡是更新过的值我都会加上。
如我想查询a[2]，那么a[2]=c[2]+c[4]+c[8]=-1+1+0=0;
查询a[3]，那么a[3]=c[3]+c[4]+c[8]=0+1+0=1。
说到这里，大家应该明白了点吧。