1. 写在题前
- 树状数组很优雅，所以就找了一道水题来找信心
- 尽量日更或者隔日更吧，之前比赛没更，所以今天补上
2. 题意
- 有n个数，，k次操作，每次操作对某个区间的所有数都+1，问第i个数最后变成了多少
3. 关于树状数组
- 非常优雅
- 数组里每个位置存的数，是这个位置坐标所管理的范围的数的和，每个坐标所管理的范围，是从这个数开始往前数2^k个，其中k是这个坐标二进制末尾0的个数
-
网上有很多教程，大家可以学习学习，在这里放出炒鸡经典的一个图
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;
}
}
