Problem Description:
We are given a M-series which is the following one :
1,2,4,8,16,32,64 …
Now you are given N numbers and Q queries of following part :
1 x y - You want to find the count of numbers between x and y which are present in M-series .
0 x y z - Change numbers from indices x and y to number z .
You have to answer the queries in the most optimal way .
Problem Type : Easy - Medium / Segment Tree + Bit Manipulation
Explanation :
A typical Segment Tree with lazy problem .
Get the input of N numbers and mark it as 1 if power of 2 otherwise 0 . Then at each node of the segment tree store the sum representing the total count of numbers with are a power of 2 uptill this point .Remember to use lazy propagation as the updates are range based instead of point based .Using this each query can be answered in log( n ) time by querying the segment tree constructed above .
Complexity : Q * log( N ) where Q are the number of queries and N is the number of array elements .
Solution : https://ideone.com/egvxEp
Related Problems:
Practice : https://www.codechef.com/problems/BYTES13
Contest : https://www.codechef.com/BYTE2016/problems/BYTES13
