title: Segment tree with lazy propagation for multiple of 3
body: <p>Abridged problem: You're given an array of n elements, initially they are all 0.</p>
  
  <p>You will receive two types of query: 0 index1 index2, in this case you have to increase by one all elements in range index1 index2(included).</p>
  
  <p>Second type: 1 index1 index2, in this case you have to print a number rapresenting how many elements between index1 and index2(included) are divisible by 3.</p>
  
  <p>Of course, as n is very large(10^6) the good approach is to use segment tree to store intervals, and also to use lazy propagation to update the tree in log n.</p>
  
  <p>But I actually really don't know how to apply lazy propagation here, because you have to keep into account three possible states for every number( may be 3k,3k+1,3k+2), and not just two as the flipping coins problem.</p>
  
  <p>If I put a flag on some interval that is included in the interval of my query, I have to update it looking at the original array and at its value, but when I have to update the son of this interval I have to do the same again and this is a wasteful of time....</p>
  
  <p>Any better idea? I search on the net but found nothing ...</p>
  
  <p>EDIT: I follow your suggestions and I code this( C++), and works for some base cases, but when I submit it I get just 10/100 points, what is wrong with it ? (I know it's a bit long and there are no much comments but it's a simple Segment Tree with lazy propagation, if you don't understand something, please tell me!</p>
  
  <p>NOTE: st[p].zero contains elements that are 0 mod 3 in interval stored in index p, st[p].one elements 1 mod 3, and st[p].two elements 2 mod 3; When I update I shift of one position these elements(0->1, 1->2, 2->0) and I use lazy. On updating, I return a pair &lt; int , pair&lt; int, int > >, just a simple way to store a triple of numbers, In this way a can return the difference of numbers 0,1,2 mod 3.</p>
  
  <pre><code>int sol;
  
  struct mod{
      mod(){ zero=0; one=0;two=0;}
      int zero;
      int one;
      int two;  
  };
  
  class SegmentTree {         
  public: int lazy[MAX_N];
    mod st[MAX_N];    
    int n;        
    int left (int p) { return p &lt;&lt; 1; }     
    int right(int p) { return (p &lt;&lt; 1) + 1; }
  
    void build(int p, int L, int R){
          if(L == R)
              st[p].zero=1;
          else{
              st[p].zero = R - L + 1;
              build(left(p), L, (L + R) / 2);
              build(right(p), ((L + R) / 2) + 1, R);
          }
          return;
    }
  
    void query(int p, int L, int R, int i, int j) {            
      if (L &gt; R || i &gt; R || j &lt; L) return; 
  
      if(lazy[p]!=0){     // Check if this no has to be updated
          for(int k=0;k&lt;lazy[p];k++){
              swap(st[p].zero,st[p].two);
              swap(st[p].one, st[p].two);
          }
          if(L != R){
              lazy[left(p)] = (lazy[left(p)] + lazy[p]) % 3;
              lazy[right(p)] = (lazy[right(p)] + lazy[p]) % 3;
          }
          lazy[p] = 0;
      } 
  
  
      if (L &gt;= i &amp;&amp; R &lt;= j) { sol += st[p].zero;   return; }              
  
  
      query(left(p) , L              , (L+R) / 2, i, j);
      query(right(p), (L+R) / 2 + 1, R          , i, j);
  
      return; 
    }          
  
    pair &lt; int, ii &gt; update_tree(int p, int L, int R, int i, int j) {
  
      if (L &gt; R || i &gt; R || j &lt; L){
        pair&lt; int, pair&lt; int, int &gt; &gt;  PP; PP.first=PP.second.first=PP.second.second=INF;
        return PP;
      }
  
      if(lazy[p]!=0){     // Check if this no has to be updated
          for(int k=0;k&lt;lazy[p];k++){
              swap(st[p].zero,st[p].two);
              swap(st[p].one, st[p].two);
          }
          if(L != R){
              lazy[left(p)] = (lazy[left(p)] + lazy[p]) % 3;
              lazy[right(p)] = (lazy[right(p)] + lazy[p]) % 3;
          }
          lazy[p] = 0;
      } 
  
      if(L&gt;=i &amp;&amp; R&lt;=j){
          swap(st[p].zero, st[p].two);
          swap(st[p].one, st[p].two);
          if(L != R){
              lazy[left(p)] = (lazy[left(p)] + 1) % 3;
              lazy[right(p)] = (lazy[right(p)] + 1) % 3;
          }
          pair&lt; int, pair&lt; int, int &gt; &gt; t; t.first = st[p].zero-st[p].one; t.second.first = st[p].one-st[p].two; t.second.second = st[p].two-st[p].zero;
          return t;
      }
  
      pair&lt; int, pair&lt; int, int &gt; &gt; s = update_tree(left(p), L, (L+R)/2, i, j); // Updating left child
      pair&lt; int, pair&lt; int, int &gt; &gt; s2 = update_tree(right(p), 1+(L+R)/2, R, i, j); // Updating right child
      pair&lt; int, pair&lt; int, int &gt; &gt; d2;
      d2.first = ( (s.first!=INF ? s.first : 0) + (s2.first!=INF ? s2.first : 0) ); // Calculating difference from the ones given by the children
      d2.second.first = ( (s.second.first!=INF ? s.second.first : 0) + (s2.second.first!=INF ? s2.second.first : 0) );
      d2.second.second = ( (s.second.second!=INF ? s.second.second : 0) + (s2.second.second!=INF ? s2.second.second : 0) );
      st[p].zero += d2.first; st[p].one += d2.second.first; st[p].two += d2.second.second; // Updating root 
      return d2;  // Return difference
    }
  
    public:
    SegmentTree(const vi &amp;_A) {
      n = (int)_A.size();            
      build(1, 0, n - 1);                                  
    }
  
    void query(int i, int j) { return query(1, 0, n - 1, i, j); }   
  
    pair&lt; int, pair&lt; int, int &gt; &gt; update_tree(int i, int j) {
      return update_tree(1, 0, n - 1, i, j); }
  };
  
  
  int N,Q;
  
  int main() {
      FILE * in; FILE * out;
      in = fopen("input.txt","r"); out = fopen("output.txt","w");
  
      fscanf(in, "%d %d" , &amp;N, &amp;Q);
      //cin&gt;&gt;N&gt;&gt;Q;
      int arr[N];
      vi A(arr,arr+N);
  
      SegmentTree *st = new SegmentTree(A);
  
      for(int i=0;i&lt;Q;i++){
          int t,q,q2; 
          fscanf(in, "%d %d %d " , &amp;t, &amp;q, &amp;q2);
          //cin&gt;&gt;t&gt;&gt;q&gt;&gt;q2;
          if(q &gt; q2) swap(q, q2);
          if(t){
              sol=0;
              st-&gt;query(q,q2);
              fprintf(out, "%d\n", sol);           
              //cout&lt;&lt;sol&lt;&lt;endl;
          }
          else{
              pair&lt;int, pair&lt; int, int &gt; &gt; t = st-&gt;update_tree(q,q2);
          }
      }
  
      fclose(in); fclose(out);
      return 0;
  }
  </code></pre>