Segment Trees #5 Range Updates and Range Queries

Counting Zeroes Problem Code: COUNZ

Problem Statement: here

Solution:

As you have seen in the title of the post, we are going to perform range updates in this question. Till now, in our series, we have only done point updates. We know point updates take O(logN) time complexity. Doing range updates will then take complexity to O(NlogN). This will surely give TLE.

So, for dealing with range updates, we use the technique of Lazy Propagation, where the complexity of Range updates boils down to O(logN).

Approach: 

We know the product will have the number of zeroes equal to :

min(num_of_2,num_of_5) in it's prime factorization, only exception being when the value itself is zero.

So, we use this thumb rule and write our functions!

Time Complexity Analysis:

1. Building Segment Tree: O(NlogM) where M is the maximum element in the array.  
1. Because For each leaf node, we need logM time for each element to figure out its factorization or simply the power of 2 and 5.
2. Update Function: 
1. It takes logN for each Query  + factorization takes logM.
3. Query Function:
1. It takes logN for each Query  + factorization takes logM.

Overall complexity: O(N*logM + Q*(logN + logM))

So, we now know the power of lazy propagation to answer range updates. It is so simple to implement and efficient to use, also it is by far the only way to tackle range updates efficiently in segment trees.

The Code:

ll n; ll a[100005]; ll tree[4*100005 + 2][3]; ll lazy[4*100005 + 2]; void process(ll ind, ll l){ tree[ind][0] = tree[ind][1] = tree[ind][2] = 0; ll num = l; if (num == 0){ tree[ind][0]++; return; } while(num%2 == 0){ tree[ind][1]++; num/=2; } while(num%5 == 0){ tree[ind][2]++; num/=5; } return; } void build(ll ind, ll l ,ll r){ if (l == r){ process(ind,a[l]); return; } ll mid = (l+r)/2; build(2*ind,l,mid); build(2*ind+1,mid+1,r); rep(i,0,3){ tree[ind][i] = tree[2*ind][i] + tree[2*ind+1][i]; } } void update(ll ind, ll l, ll r, ll us, ll ue, ll val){ //First Step - Never we go down if you have lazy value at node, first resolve it if (lazy[ind] != -1){ process(ind,lazy[ind]); rep(i,0,3){ tree[ind][i] *= (r-l+1); } //if not a leaf node, pass on the lazy value if ( l!=r ){ lazy[2*ind] = lazy[2*ind + 1] = lazy[ind]; } // Lazy value resolved. lazy[ind] = -1; } if (r < us || l > ue){ return; } if (l >= us and r <= ue){ process(ind,val); rep(i,0,3){ tree[ind][i] *= (r-l+1); } if ( l!=r ){ lazy[2*ind] = lazy[2*ind + 1] = val; } return; } ll mid = (l+r)/2; update(2*ind,l,mid,us,ue,val); update(2*ind+1,mid+1,r,us,ue,val); rep(i,0,3){ tree[ind][i] = tree[2*ind][i] + tree[2*ind+1][i]; } } V(ll) query(ll ind, ll l,ll r, ll qs, ll qe){ //First Step - Never we go down if you have lazy value at node, first resolve it if (lazy[ind] != -1){ process(ind,lazy[ind]); rep(i,0,3){ tree[ind][i] *= (r-l+1); } //if not a leaf node, pass on the lazy value if ( l!=r ){ lazy[2*ind] = lazy[2*ind + 1] = lazy[ind]; } // Lazy value resolved. lazy[ind] = -1; } if (r < qs || l> qe){ V(ll) v(3,0); return v; } if (l>= qs and r<=qe){ V(ll) v(3,0); rep(i,0,3) v[i] = tree[ind][i]; return v; } ll mid = (l+r)/2; V(ll) left = query(2*ind, l, mid, qs,qe); V(ll) right = query(2*ind+1,mid+1,r,qs,qe); V(ll) v(3,0); rep(i,0,3) v[i] = left[i] + right[i]; return v; } void solve() { clr(lazy,-1); cin >> n; rep(i,0,n) cin >> a[i]; build(1,0,n-1); ll q; cin >> q; rep(i,0,q){ ll t; cin >> t; if (t == 0){ ll l,r,v; cin >> l >> r >> v; update(1,0,n-1,--l,--r,v); } else{ ll l,r; cin >> l >> r; V(ll) ans = query(1,0,n-1,--l,--r); if (ans[0]){ cout << 1 << endl; } else{ cout << min(ans[1],ans[2]) << endl; } } } } int32_t main(){ ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t=1; // cin>>t; test(t){ solve(); } return 0; }