带lazy主要为了节省不必要的时间
多用于修改一段区间值
1 struct Segment_tree{ 2 int L[maxn*4],R[maxn*4],val[maxn*4],add[maxn*4]; 3 4 void lazy(int pos){ //懒惰标记 5 val[pos<<1] = add[pos]*(R[pos<<1] - L[pos<<1] + 1); 6 val[pos<<1|1] = add[pos]*(R[pos<<1|1] - L[pos<<1|1] + 1); 7 add[pos<<1] = add[pos]; 8 add[pos<<1|1] = add[pos]; 9 add[pos] = 0; 10 } 11 12 void build(int pos,int l,int r,int *num){ 13 L[pos] = l; 14 R[pos] = r; 15 add[pos] = 0; 16 if(l == r){ 17 val[pos] = num[l]; 18 return; 19 } 20 int mid = (l+r) >> 1; 21 build(pos<<1,l,mid,num); 22 build(pos<<1|1,mid+1,r,num); 23 val[pos] = val[pos<<1]+val[pos<<1|1]; 24 } 25 26 void update(int pos,int l,int r,int v){ 27 if(L[pos] == l&&R[pos] == r){ 28 val[pos] = v*(r-l+1); 29 add[pos] = v; 30 return; 31 } 32 if( add[pos] ) lazy(pos); //下放 33 int mid = (L[pos]+R[pos]) >> 1; 34 if(r <= mid){ 35 update(pos<<1,l,r,v); 36 } 37 else if(l > mid){ 38 update(pos<<1|1,l,r,v); 39 } 40 else{ 41 update(pos<<1,l,mid,v); 42 update(pos<<1|1,mid+1,r,v); 43 } 44 val[pos] = val[pos<<1] + val[pos<<1|1]; 45 } 46 47 int query(int pos,int l,int r){ 48 if(L[pos] == l && R[pos] == r){ 49 return val[pos]; 50 } 51 if( add[pos] ) lazy(pos); //下放 52 int mid = (L[pos] + R[pos]) >> 1; 53 if(r <= mid) return query(pos<<1,l,r); 54 else if(l > mid) return query(pos<<1|1,l,r); 55 else{ 56 return query(pos<<1,l,mid)+query(pos<<1|1,mid+1,r); 57 } 58 } 59 }tre;