Problem Link:
Difficulty:
Medium
Problem:
You are given a bit-string containing all zeroes initially. Now you have to perform two operations.
First is to flip the bits between two given indices x and y. And second is to answer how many ones are there in between two indices x and y.
Explanation:
One way to solve this problem will be using a linear array. Then follow a linear approach to perform the operations. Whenever we want to apply the first operation. We will loop through x to y and flip the respective bit of the string. And for the second operation, we will loop through x to y and count the numbers of 1s. This method is not very efficient as it will take O(n) for update and O(n) for query. Which will definitely exceed the time limit of the problem.
A better way is to use the segment tree with lazy propagation. In segment tree, the leaf nodes of the tree are elements of the array. And their parents can contain any query over them. Here in this case, numbers of 1s. A lazy segment tree is also needed for the lazy update. Thus, in this case, the solution will take O(log(n)) for update and O(log(n)) for query. And it is well within the time limits of the problem.
To know more about Segment Tree, Click here.
Solution
Author’s solution can be found here.
