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 : egvxEp - Online C++0x Compiler & Debugging Tool - Ideone.com
Related Problems:
Practice : BYTES13 Problem - CodeChef
Contest : CodeChef: Practical coding for everyone
