线段树
cpp
struct SegmentTree{
struct Node{
int l,r,mx,mn,sum;
};
vector<Node> t;
void init(int n){
t=vector<Node>(n<<2);
}
void build(int p,int l,int r){
t[p]={l,r,0,0,0};
if(l==r)return;
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
void pushup(int p){
auto &u=t[p],&l=t[p<<1],&r=t[p<<1|1];
u.sum=l.sum+r.sum;
u.mx=max(l.mx,r.mx);
u.mn=min(l.mn,r.mn);
}
void modify(int p,int x,int y){
if(t[p].l==t[p].r){
t[p].mx=t[p].mn=t[p].sum=y;
return;
}
int mid=t[p].l+t[p].r>>1;
if(x<=mid)modify(p<<1,x,y);
else modify(p<<1|1,x,y);
pushup(p);
}
int query_max(int p,int l,int r){
if(l<=t[p].l&&r>=t[p].r)return t[p].mx;
int mid=t[p].l+t[p].r>>1;
int ans=0;
if(l<=mid)ans=max(ans,query_max(p<<1,l,r));
if(r>mid)ans=max(ans,query_max(p<<1|1,l,r));
return ans;
}
int query_min(int p,int l,int r){
if(l<=t[p].l&&r>=t[p].r)return t[p].mn;
int mid=t[p].l+t[p].r>>1;
int ans=INF;
if(l<=mid)ans=min(ans,query_min(p<<1,l,r));
if(r>mid)ans=min(ans,query_min(p<<1|1,l,r));
return ans;
}
int query_sum(int p,int l,int r){
if(l<=t[p].l&&r>=t[p].r)return t[p].sum;
int mid=t[p].l+t[p].r>>1;
int ans=0;
if(l<=mid)ans+=query_sum(p<<1,l,r);
if(r>mid)ans+=query_sum(p<<1|1,l,r);
return ans;
}
};