就是裸的区间更新：
相对于直观的线段树的区间更新，树状数组的区间更新原理不太相同：由于数组中的一个结点控制的是一块区间，当遇到更新【l，r】时，先将所有能控制到 l 的结点给更新了，这样一来就是一下子更新到【l，+无穷】了，所以需要将【r+1，+无穷】区间的更新消去，那么同理，【r+1，+无穷】反向减掉相同的数即可
#include<bits/stdc++.h> using namespace std; #define maxn 100005 int bit[maxn],a,b,n; void add(int x,int num){ for(int i=x;i<=100000;i+=i&-i) bit[i]+=num; } int query(int x){ int res=0; for(int i=x;i;i-=i&-i) res+=bit[i]; return res; } int main(){ while(scanf("%d",&n),n){ memset(bit,0,sizeof bit); for(int i=1;i<=n;i++){ scanf("%d%d",&a,&b); add(a,1);add(b+1,-1); } for(int i=1;i<n;i++) printf("%d ",query(i)); printf("%d\n",query(n)); } }
转载于:https://www.cnblogs.com/zsben991126/p/10098957.html
