#include<bits/stdc++.h> using namespace std; const int lim = 100010; int n,c[lim];// 記錄差分變化 void update(int a,int val){while(a<=n){c[a]+=val;a+=a&(-a);} } int get(int x){int sum=0;while(x){sum+=c[x];x-=x&(-x);}return sum; } int main() {while(scanf("%d",&n),n){int a,b;int tmp = n; while(tmp--){scanf("%d%d",&a,&b);update(a,1);update(b+1,-1);}for(int i=1;i<=n;i++){printf("%d%c",get(i),i==n?'\n':' ');}memset(c,0,sizeof(c)); }return 0; }

差分技巧的運用

也就是對于一個序列
我們假設(shè)
array a :1 2 3 4 5
array b :1 1 1 1 1
上面的是原數(shù)組下面的是差分?jǐn)?shù)組
我們可以得知 其中的一個元素
有性質(zhì) a[i] = Sigma(i=1 to i) bi
并且當(dāng)我們得到如果在2,3上區(qū)間更新加2
那么
a: 1 4 5 4 5
b: 1 3 1 -1 1
可知 只有2，4變化 2加了2 而4減了2
所以啊
只有在區(qū)間邊界才會差分才會變化
那么當(dāng)我們單點求某個值時
我們就可以用樹狀數(shù)組維護(hù)前綴和了

總結(jié)

以上是生活随笔為你收集整理的HDU 1566 Count the Colors 树状树组 区间更新 单点求值的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。