title: Lazy propagation in segment tree?
body: <p>Well, I was trying to solve this <a href="http://www.codechef.com/problems/FLIPCOIN/" rel="nofollow">Flipping coins</a> problem on Codechef. Am solving it with segment trees. But getting time limit exceed. I searched and found that I have to use lazy propagation. But I am unable to understand. My update function works recursively(top to bottom). Please give some hints or explain it with example. Also point out where I have to change the code. </p>
  
  <p>In flipping coins, during update if a node value is 1 change it to 0 and if it is 0 change it to 1.</p>
  
  <p>start and end are limits of original array. tree is segment tree array.</p>
  
  <pre><code>void update(int node, int start, int end,int pos)//pos=position to update
  {
      if(start==end) tree[node]=(tree[node]==0) ? 1 : 0;
      else
      {
          int mid=(start+end)/2;
          if(mid&gt;=pos) update(2*node + 1, start, mid, pos);
          else update(2*node + 2, mid+1, end, pos);
  
          tree[node]=tree[2*node +1] + tree[2*node +2];
      }
  }
  </code></pre>