時間復雜度為什麼是log(n)?
首先樹狀數組的思想本身就是一個樹，所以在操作的時間復雜度上面和樹相似
還可以通過計算來論證：
假設現在的節點是n，那麼到達父節點的方法就是：
n=n+n&-n (不知道為什麼這樣寫的，自行百度)
實際上就是把n的二進制最左邊的1向左移動了一位，比如2-10,4-100
到達子節點的方法就是：
n=n-n&-n
這個實際上就是每次把最左邊的1變成0，比如7-111,6-110,4-100
那麼這樣二進制的位移運算的時間復雜度是log(n)，所以樹狀數組查詢和統計的時間復雜度也為log(n)
解題思路
這道題可以用很多方法來做，線段樹是最容易想到的，但是代碼實現上很復雜
其實這道題可以把每次染色的點抽象為每次塗改的區間，然後對要查詢的點所在區間的更新次數進行求和
這樣就可以在時間上，大大縮短，查詢和統計的時間復雜度都為log(n)
樹狀數組中的每個節點都代表了一段線段區間，每次更新的時候，根據樹狀數組的特性可以把b以前包含的所有區間都找出來，然後把b以前的區間全部加一次染色次數。然後，再把a以前的區間全部減一次染色次數，這樣就修改了樹狀數組中的[a,b]的區間染色次數，查詢每一個點總的染色次數的時候，就可以直接向上統計每個父節點的值，就是包含這個點的所有區間被染色次數，這就是樹狀數組中向下查詢，向上統計的典型應用
Ps:根據個人理解層次的不同，這道題也可以向上查詢，向下統計，還可以向下查詢，向下統計，不過我寫的這種是最容易理解的
代碼實現如下：
用cin,cout進行讀寫操作的話，會超時，所以我還是用的scanf()，printf()
[cpp]
#include <stdio.h>
#include <string.h>
const int MAXN=110000;
int n,c[MAXN];
int lowbit(int x)
//計算2^k
{
x=x&-x;
return x;
}
void update(int num,int val)
//向下查詢，num是要更新的子節點，val是要修改的值
{
while(num>0)
{
c[num]+=val;
num-=lowbit(num);
}
}
int getSum(int num)
//向上統計每個區間被染色的次數
{
int sum=0;
while(num<=n)
{
sum+=c[num];
num+=lowbit(num);
}
return sum;
}
int main()
{
int a,b;
while(scanf("%d",&n),n)
{
memset(c,0,sizeof(c));
for(int i=0;i<n;i++)
{
scanf("%d%d",&a,&b);
//將b以下區間+1
update(b,1);
//將a以下區間-1
update(a-1,-1);
}
for(int j=1;j<n;j++)
{
printf("%d ",getSum(j));
}
printf("%d\n",getSum(n));
}
return 0;
}
#include <stdio.h>
#include <string.h>
const int MAXN=110000;
int n,c[MAXN];
int lowbit(int x)
//計算2^k
{
x=x&-x;
return x;
}
void update(int num,int val)
//向下查詢，num是要更新的子節點，val是要修改的值
{
while(num>0)
{
c[num]+=val;
num-=lowbit(num);
}
}
int getSum(int num)
//向上統計每個區間被染色的次數
{
int sum=0;
while(num<=n)
{
sum+=c[num];
num+=lowbit(num);
}
return sum;
}
int main()
{
int a,b;
while(scanf("%d",&n),n)
{
memset(c,0,sizeof(c));
for(int i=0;i<n;i++)
{
scanf("%d%d",&a,&b);
//將b以下區間+1
update(b,1);
//將a以下區間-1
update(a-1,-1);
}
for(int j=1;j<n;j++)
{
printf("%d ",getSum(j));
}
printf("%d\n",getSum(n));
}
return 0;
}
