BYTES13 - Editorial

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

Can someone please point out whats wrong with this code ? It would be very helpful. ( I am trying to solve it without lazy propagation)

Question link(BYTES13)

Thanks :slight_smile:

//