• 編輯：數(shù)字_ID
• 2018年5月21日

1. 寫(xiě)在題前

• 樹(shù)狀數(shù)組很優(yōu)雅，所以就找了一道水題來(lái)找信心
• 盡量日更或者隔日更吧，之前比賽沒(méi)更，所以今天補(bǔ)上

2. 題意

• 有n個(gè)數(shù)，，k次操作，每次操作對(duì)某個(gè)區(qū)間的所有數(shù)都+1，問(wèn)第i個(gè)數(shù)最后變成了多少

3. 關(guān)于樹(shù)狀數(shù)組

• 非常優(yōu)雅
• 數(shù)組里每個(gè)位置存的數(shù)，是這個(gè)位置坐標(biāo)所管理的范圍的數(shù)的和，每個(gè)坐標(biāo)所管理的范圍，是從這個(gè)數(shù)開(kāi)始往前數(shù)2^k個(gè)，其中k是這個(gè)坐標(biāo)二進(jìn)制末尾0的個(gè)數(shù)

• 網(wǎng)上有很多教程，大家可以學(xué)習(xí)學(xué)習(xí)，在這里放出炒雞經(jīng)典的一個(gè)圖
  樹(shù)狀數(shù)組.png

4. 關(guān)于這道題

• 這道題有一個(gè)很有意思的地方，一般樹(shù)狀數(shù)組是求前綴和的，但通過(guò)某種操作，可以用來(lái)求單個(gè)點(diǎn)的值，這種操作使得區(qū)間修改的復(fù)雜度大大降低
• 首先來(lái)看題目，是要對(duì)某個(gè)區(qū)間進(jìn)行加固定值的操作，對(duì)于樹(shù)狀數(shù)組，每改變一個(gè)值，就要進(jìn)行O（logn）的復(fù)雜度來(lái)修改某些前綴和，對(duì)于n個(gè)點(diǎn)，復(fù)雜度就變成了O（nlogn）。然而這道題有這么一種更簡(jiǎn)單的做法，對(duì)（i,j）區(qū)間進(jìn)行每個(gè)數(shù)加一個(gè)v，只需要對(duì)第i個(gè)位置加v，對(duì)第j+1個(gè)數(shù)-v，這樣每個(gè)位置的前綴和就是該位置最終的數(shù)，非常的巧妙，大家可以自己思索一些，很優(yōu)雅

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;
    } 
}