1 namespace Seg{
 2     struct segnode{
 3         int S,E,len,mid;
 4         int Min, Tag;
 5         segnode *L,*R;
 6         segnode(int l,int r,int *base):S(l),E(r),len(r-l),mid(l+(len>>1)){
 7             Tag = 0;
 8             if(len == 1){Min = base[l],L = R = NULL;return;}
 9             L = new segnode(l,mid,base);
10             R = new segnode(mid,r,base);
11             Min = min(L->Min,R->Min);
12         }
13         ~segnode(){if(L!=NULL)delete L,delete R;}
14         int GetMin(int l,int r){
15             if(l==S && r==E)return Tag + Min;
16             if(l >= mid)return Tag + R->GetMin(l,r);
17             if(r <= mid)return Tag + L->GetMin(l,r);
18             return Tag + min(L->GetMin(l,mid),R->GetMin(mid,r));
19         }
20         void Update(int loc, int val){
21             if(len == 1){
22                 Min = val;
23                 return;
24             }
25             if(loc < mid)L -> Update(loc, val);
26             else R -> Update(loc, val);
27             Min = min(L->Tag+L->Min,R->Tag+R->Min);
28         }
29         void AddRng(int l,int r,int k){
30             if(l==S && r==E){Tag += k;return;}
31             if(l >= mid)R->AddRng(l,r,k);
32             else if(r <= mid)L->AddRng(l,r,k);
33             else L->AddRng(l,mid,k),R->AddRng(mid,r,k);
34             Min = min(L->Tag+L->Min,R->Tag+R->Min);
35         }
36     };
37     struct segtree {
38         segnode *Root;
39         segtree(int *l,int *r){Root = new segnode(0,r-l,l);}
40         ~segtree(){delete Root;}
41         int GetMin(int l,int r){return Root->GetMin(l,r);}
42         void AddRng(int l,int r,int k){Root->AddRng(l,r,k);}
43     };
44 }