【算法】线段树

【注意】修改或查询区间时，若区间能包含某棵子树就立即返回，否则线段树就失去了意义。

#include
      
       #include
       
        using namespace std;const int inf=0x3f3f3f3f;struct treess{
    int l,r,ms;}t[300010];int a[100010],n,m,tot,anss[100010];void build(int k,int l,int r){    t[k].l=l;t[k].r=r;    if(l==r){t[k].ms=a[l];return;}    int mid=(l+r)>>1;    build(k<<1,l,mid);    build(k<<1|1,mid+1,r);    t[k].ms=min(t[k<<1].ms,t[k<<1|1].ms);//    printf("[%d] l=%d r=%d mins=%d\n",k,t[k].l,t[k].r,t[k].ms);}void insert(int k,int x,int y){    int left=t[k].l,right=t[k].r;    if(left==right)t[k].ms=y;     else      {          int mid=(left+right)>>1;          if(x<=mid)insert(k<<1,x,y);          else insert(k<<1|1,x,y);        t[k].ms=min(t[k<<1].ms,t[k<<1|1].ms);      }}int ask(int k,int l,int r){    int left=t[k].l,right=t[k].r;    if(l<=left&&right<=r)return t[k].ms;     else      {          int mid=(left+right)>>1,ans=inf;          if(l<=mid)ans=ask(k<<1,l,r);          if(r>mid)ans=min(ans,ask(k<<1|1,l,r));          return ans;      }}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)scanf("%d",&a[i]);    build(1,1,n);    for(int i=1;i<=m;i++)     {         int p,x,y;         scanf("%d%d%d",&p,&x,&y);         if(p==1)anss[++tot]=ask(1,x,y);          else insert(1,x,y);     }    for(int i=1;i