Templates/SegmentTree.cpp at main · aheel03/Templates · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>
using namespace std;

typedef long long int            ll;
typedef unsigned long long int   ull;
typedef vector<pair<ll,ll>>      vpll;
typedef vector<ll>               vll;
typedef map<ll,ll>               mll;
typedef pair<ll,ll>              pll;

#define loop(i,k,n)              for(ll i=k;i<n;i++)
#define pb                       push_back
#define ft                       first
#define sc                       second
#define yes                      cout<<"Yes"<<endl
#define no                       cout<<"No"<<endl
#define Yes                      cout<<"YES"<<endl
#define No                       cout<<"NO"<<endl
#define Alice                    cout<<"Alice"<<endl
#define Bob                      cout<<"Bob"<<endl
#define newl                     cout<<"\n"
#define clean                    fflush(stdout)
#define FLOOR(x,y)               (ll(floor(double(x)/y)))
#define CEIL(x,y)                (ll(ceil(double(x)/y)))
#define max3(a,b,c)              max(a,max(b,c))
#define min3(a,b,c)              min(a,min(b,c))
#define all(v)                   v.begin(),v.end()
#define rall(v)                  v.rbegin(),v.rend()
#define Max(v)                   *max_element(v.begin(), v.end())
#define Min(v)                   *min_element(v.begin(), v.end())
#define SORT(a)                  sort(a,a+(sizeof(a)/sizeof(a[0])))
#define inparr(arr,n)            ll arr[n]; loop(i,0,n) cin >> arr[i]
#define inpvec(v,n)              vll v(n); for(auto &i:v) cin >> i
#define prec(ans,n)              cout<< fixed << setprecision(n) << ans << endl
const ll M=998244353;
const ll N=2e5+5;
const ll INF=1e15;

ll segtree[N*4];
ll a[N];

ll func(ll a,ll b){
    return min(a,b);
}


void build_segtree(ll node, ll lo, ll hi){
    if(lo==hi){
        segtree[node]=a[lo];
        return;
    }
    ll mid=(lo+hi)/2;
    build_segtree(node*2,lo,mid);
    build_segtree((node*2)+1,mid+1,hi);
    segtree[node]=func(segtree[node*2],segtree[(node*2)+1]);
}

ll query(ll node, ll lo, ll hi, ll l, ll r){
    if(r<lo || l>hi){
        return INF;
    }
    if(l<=lo && r>=hi){
        return segtree[node];
    }
    ll mid=(lo+hi)/2;
    ll left=query(node*2,lo,mid,l,r);
    ll right=query((node*2)+1,mid+1,hi,l,r);
    return func(left,right);
}

void update(ll node, ll lo, ll hi, ll pos, ll u){
    if(lo==hi){
        segtree[node]=u;
        return;
    }
    ll mid=(lo+hi)/2;
    if(pos<=mid){
        update(node*2,lo,mid,pos,u);
    }else{
        update(node*2+1,mid+1,hi,pos,u);
    }

    segtree[node]=func(segtree[node*2],segtree[node*2+1]);
}


int main()
{
    ll n,q;
    cin>>n>>q;
    loop(i,1,n+1){
        cin>>a[i];
    }
    build_segtree(1,1,n);
    loop(i,0,q){
        ll inp,l,r;
        cin>>inp>>l>>r;
        if(!(inp&1)){
            cout<<query(1,1,n,l,r)<<endl;
        }else{
            update(1,1,n,l,r);
        }
    }
}