Toggle and count all 1's !

Revision en4, by atlasworld, 2019-02-04 17:58:16

You are given a binary array consists of 0's and 1's , and q queries . q can be large !

in each query you are given a certain range [L , R].

suppose a[] = {1,0,0,1}

L = 1 , R = 3 .

do toggling , resultant array = {0,1,1,1}

L = 1 , R =4

count all one's , ans = 3.

you have to either toggle bits in the given range i.e make 0 = 1 and 1 = 0 .

and on another query you are about to count all 1's in the range of [L,R]. **** The problem gives a feel of segment tree + lazy propogation . but how to do toggling in segment tree .

how should we update the lazy tree !

Any idea !

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English atlasworld 2019-02-04 17:58:16 14
en3 English atlasworld 2019-02-04 17:58:00 135
en2 English atlasworld 2019-02-04 17:55:20 12
en1 English atlasworld 2019-02-04 17:54:54 490 Initial revision (published)