【数字_ID】HDU-1556-Color the ball（树

• 编辑：数字_ID
• 2018年5月21日

1. 写在题前

• 树状数组很优雅，所以就找了一道水题来找信心
• 尽量日更或者隔日更吧，之前比赛没更，所以今天补上

2. 题意

• 有n个数，，k次操作，每次操作对某个区间的所有数都+1，问第i个数最后变成了多少

3. 关于树状数组

• 非常优雅
• 数组里每个位置存的数，是这个位置坐标所管理的范围的数的和，每个坐标所管理的范围，是从这个数开始往前数2^k个，其中k是这个坐标二进制末尾0的个数
• 网上有很多教程，大家可以学习学习，在这里放出炒鸡经典的一个图 树状数组.png

4. 关于这道题

• 这道题有一个很有意思的地方，一般树状数组是求前缀和的，但通过某种操作，可以用来求单个点的值，这种操作使得区间修改的复杂度大大降低
• 首先来看题目，是要对某个区间进行加固定值的操作，对于树状数组，每改变一个值，就要进行O（logn）的复杂度来修改某些前缀和，对于n个点，复杂度就变成了O（nlogn）。然而这道题有这么一种更简单的做法，对（i,j）区间进行每个数加一个v，只需要对第i个位置加v，对第j+1个数-v，这样每个位置的前缀和就是该位置最终的数，非常的巧妙，大家可以自己思索一些，很优雅

5. 代码

#include<string.h>
#include<stdio.h>
#include<iostream>

using namespace std;


#define lowbit(x) (x&(-x))
const int maxn = 100020;

int n;
int a,b;
int sum[maxn];
void add(int pos,int val)
{
    while(pos<=n)
    {
        sum[pos] += val;
        pos += lowbit(pos);
    }
}

int query(int pos)
{
    int res = 0;
    while(pos>0)
    {
        res += sum[pos];
        pos -= lowbit(pos);
    }
    return res;
}
int main()
{
    while(cin>>n&&n!=0)
    {
        memset(sum,0,sizeof(sum));
        for(int i = 0;i<n;i++)
        {
            cin>>a>>b;
            add(a,1);
            add(b+1,-1);
        }
        for(int i = 1;i<=n;i++)
        {
            if(i == 1)cout<<query(i);
            else cout<<" "<<query(i);
        }
        cout<<endl;
    } 
}