题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1556
题意就不再赘述，说下解题思路：这道题目是树状数组区间查询点更新的题目，所谓的区间更新就是更新区间[l,r]里的每一个数，点查询则是只查询某一点的值，和以前经常遇见的更新某点查询区间是相反过来的。通过对树状数组存储结构的观察，单纯的把区间内的每一个点都更新是不可能的，不过我们可以给某些点加些标记。我们知道树状数组tree[]里存储的是当前坐标的前缀和，update()更新的是当前坐标往后通过lowbit()计算出来下标的tree[]值，所以当要更新[l,r]区间的值得时候，update(l,1),update(r+1,-1)则就会使得在这个区间[l,r]内的增加的和相当于更新每一个点增加的和。这时候我们通过query(i)操作就可以求出当前i点的值。
为什么query(i)求出的是当前i点的值呢？
在进行更新区间的时候，我们把l往后的区间更新+1，r+1往后的区间更新-1，假设存在一点i，
①该点不在已更新的区间[l,r]内，也就是说该点的现在的值应该就是0，如果i < l,则i从未增加，一定为0，如果i > r,则在进行update()更新的时候，update(l,1)和update(r+1,-1)，如果i点是l和r的公共父节点，则在进行两次update()操作后该点值仍为0，当i为某两个点的公共父节点时，观察树状数组存储结构可知，i - = lowbit(i)则一定为0，所以该点前缀和为该点的值；如果i点为r+1的父节点，则当前i点的值为-1， i -= lowbit(I)的值一定为l点的父节点值，且再执行-lowbit(i)后的值一定为0，所以也可指当前点前缀和也为0；如果i点是l的父节点，又因r > l,则i点可能是r点的父节点，和上述情况类似就不再叙述，当i不是r的父节点的时候，则i就一定不是l的父节点，在更新的时候则不会对i进行操作。
②当i点在区间[l,r]内时，待更新.......
所以通过update(l,1)和update(r+1,-1)两次操作后的query(i)值为当前点的值。
AC代码如下：
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 1e5 + 5; int tree[maxn],n; int lowbit(int k){ return k & -k; } void update(int k, int num){ while(k <= n){ tree[k] += num; k += lowbit(k); } } int query(int k){ int sum = 0; while(k){ sum += tree[k]; k -= lowbit(k); } return sum; } int main(){ while(~scanf("%d",&n)){ if(n == 0) break; memset(tree,0,sizeof(tree)); int a,b; for(int i = 1; i <= n; i ++){ scanf("%d%d",&a,&b); update(a,1); // for(int j = 1; j <= n; j ++) printf("%d ",tree[j]);printf("\n"); update(b+1,-1); // for(int j = 1; j <= n; j ++) printf("%d ",tree[j]);printf("\n"); } for(int i = 1; i <= n; i ++){ if(i > 1) printf(" "); printf("%d",query(i)); } printf("\n"); } return 0; }