首页 > 代码库 > HIHO 线段树(单点)

HIHO 线段树(单点)

 1 #include <stdio.h> 2 #include <string.h> 3 #include <math.h> 4 #include <iostream> 5 #include <algorithm> 6 using namespace std; 7 const int MM=1000000;//10^6 8 int num[MM<<2]; 9 void buildtree(int l,int r,int id)10 {11     if(l==r)12         {scanf("%d",&num[id]);return;}13     else14     {15         int mid=(r+l)>>1;16         buildtree(l,mid,id<<1);17         buildtree(mid+1,r,id<<1|1);18     }19     num[id]=min(num[id<<1],num[id<<1|1]);20 21 }22 int query(int L,int R,int l,int r,int id)23 {24     int minn=0x7fffffff;25     if (L <= l && r <= R) {26         return num[id];27     } 28     else {29         int mid=(r+l)>>1;30         if(L<=mid)minn=min(minn,query(L,R,l,mid,id<<1));31         if(R>mid)minn=min(minn,query(L,R,mid+1,r,id<<1|1));32         num[id]=min(num[id<<1], num[id<<1|1]);33         return minn;34     }35 }36 void change(int pos,int e,int l,int r,int id)37 {38     if(l==r)39         {num[id]=e;return;}40     else41     {42         int mid=(r+l)>>1;43         if(pos<= mid)44             change(pos,e,l,mid,id<<1);45         else change(pos,e,mid+1,r,id<<1|1);46     }47     num[id]=min(num[id<<1],num[id<<1|1]);48 49 }50 int main(){51     int i,n,que,number,x,y,z;52     n=1;53     while(n--)54     {55         cin>>number;56         buildtree(1,number,1);57         cin>>que;58         //cout << "ok" << endl;59         for(i=0;i<que;i++)60         {61             scanf("%d%d%d",&x,&y,&z);62             //cout << x << " " << y << " " << z << endl;63             if(x==0)64             {65                 int ans=query(y,z,1,number,1);66                 printf("%d\n",ans );67             }68             else change(y,z,1,number,1);69         }70 71     }72  return 0;73 }

 

HIHO 线段树(单点)