线段树成段更新模板-杭电1556

#include <iostream> #include <cstdio> #include <cstring> #define left L,m,rt<<1 #define right m+1,R,rt<<1|1 #define maxn 100050 int flag; int sum[maxn<<2]; void down(int rt) { if(sum[rt]) { sum[rt<<1]+=sum[rt]; sum[rt<<1|1]+=sum[rt]; sum[rt]=0; } } void update(int a,int b,int c,int L,int R,int rt) { if(a<=L&&b>=R) { sum[rt]+=c; return; } down(rt); int m=(L+R)/2; if(a<=m) { update(a,b,c,left); } if(b>m) { update(a,b,c,right); } } void Quary(int L,int R,int rt) { if(L==R) { if(flag) { printf("%d",sum[rt]); flag=0; } else printf(" %d",sum[rt]); return ; } down(rt); int m=(L+R)/2; Quary(left); Quary(right); } int main() { int N,a,b,i,j; while(~scanf("%d",&N)&&N) { memset(sum,0,sizeof(sum)); flag=1; for(i=1;i<=N;i++) { scanf("%d%d",&a,&b); update(a,b,1,1,N,1); } Quary(1,N,1); printf("\n"); } return 0; }