atlasworld's blog

By atlasworld, history, 8 months ago, In English,

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 !

 
 
 
 
  • Vote: I like it
  • +6
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Just use the trick that inverting a bit x can be done by taking  - x + 1.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hey .. sorry but i couldnt understand a single thing .. it would be very helpful if u elaborate it quite a bit.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      What I am saying is that toggling a bit is the same thing as multiplying it with -1 and then adding 1. The nice thing about this is that there are lazy segment trees that support doing addition and multiplication and sum/max/min on intervals, so for me solving this problem would just be applying a very general lazy segment tree.

      I think that if you want to learn lazy segment trees then first try to implement a general lazy segment tree that support addition, multiplication, sum/min/max. After that you can solve nearly all segment tree problems using that one tree, so it is quite useful.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i have seen it before posting. but how to use segment tree with lazy is not explaimed clearly there. if u could understand please let me know .

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Lazy tags store if each range should be toggled. When a range is toggled, set tree[node] = en-st+1 - tree[node]; which uses the fact that toggling a bit value x is the same as doing x=1-x.

      • »
        »
        »
        »
        8 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        so segment tree is storing the count of 1's in the range [l,r] ? and when we do lazy propogation , what value will we propogate ?

        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          yes

          • »
            »
            »
            »
            »
            »
            8 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            so suppose while toggling a given range , how should we do propogation in lazy tree ?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I wrote a code for a similar problem. https://pastebin.com/R7iqy1sq Reply if you don't understand.

  • »
    »
    8 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Thanks ! Actually I was having difficulty with lazy part .What lazy will store and propogate. Now I understood , lazy[node] will store either 0 or 1 . 1 means there are some previous toggles which we have not did earlier and now we have to do when we are visiting the current node in segment tree. __ Thanks for help . the problem i encountered when i was solving 877E . now get it!

    Thanks starbot