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     else
14     {
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     else
41     {
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
",ans );
67             }
68             else change(y,z,1,number,1);
69         }
70 
71     }
72  return 0;
73 }