1 struct Segment_tree
  2 {
  3     int size;
  4     int *node;
  5     void build(int n)
  6     {
  7         n+=4;
  8         size=1;
  9         while(size<n)
 10             size<<=1;
 11         node=new int[size+size+4];
 12     }
 13     void updata(int pos)
 14     {
 15         int A=max(node[pos<<1],node[pos<<1^1]);
 16         node[pos<<1]-=A;
 17         node[pos<<1^1]-=A;
 18         node[pos]+=A;
 19     }
 20     void build(int n,int arr[])
 21     {
 22         build(n);
 23         int i;
 24         memset(node,0,8*size);
 25         for(i=1; i<=n; i++)
 26         {
 27             node[i+size]=arr[i];
 28             //printf("%d ",arr[i]);
 29         }
 30         //printf("size =%d",size);
 31         //puts("");
 32         for(i=size-1; i>0; i--)
 33         {
 34             updata(i);
 35         }
 36     }
 37     void add(int l,int r,int d)
 38     {
 39         l+=size-1;
 40         r+=size+1;
 41         int A;
 42         for(; r^l^1; l>>=1,r>>=1 )
 43         {
 44             if(~l&1)
 45                 node[l^1]+=d;
 46             if(r&1)
 47                 node[r^1]+=d;
 48             updata(l>>1);
 49             updata(r>>1);
 50         }
 51         while(l>1)
 52         {
 53             updata(l>>=1);
 54         }
 55     }
 56     int RMQ(int l,int r)
 57     {
 58         l+=size;
 59         r+=size;
 60         int ans,lans=0,rans=0;
 61         if(l!=r)
 62         {
 63             for(; r^l^1; l>>=1,r>>=1 )
 64             {
 65                 lans+=node[l];
 66                 rans+=node[r];
 67                 if(~l&1)
 68                     lans=max(lans,node[l^1]);
 69                 if(r&1)
 70                     rans=max(rans,node[r^1]);
 71             }
 72         }
 73         ans=max(lans+node[l],rans+node[r]);
 74         while(l>1)
 75         {
 76             ans+=node[l>>=1];
 77         }
 78         return ans;
 79     }
 80     void put()
 81     {
 82         int i=1,j=1,s=size*4,k,len=3;
 83         for(i=1; i<=2*size-1; i++)
 84         {
 85             if(i==j)
 86             {
 87                 puts("");
 88                 j<<=1;
 89                 s>>=1;
 90                 for(k=0; k<len*(s/2-1); k++)
 91                     printf(" ");
 92 
 93             }
 94             printf("%3d",node[i]);
 95             for(k=0; k<len*(s-1); k++)
 96                 printf(" ");
 97 
 98         }
 99         puts("");
100     }
101 } tree;