Coding-Library/segment_tree_min_max_index.cpp at master · saikuNoCoda/Coding-Library · 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
const ll MAXN = 1e5 + 10;
pair<ll,ll> a[MAXN];

pair<ll,ll> seg_min[4*MAXN];
pair<ll,ll> seg_max[4*MAXN];

void update(ll node,ll s,ll e,ll pos,ll val){

    if(s > e) return;

    if(s == e){
        seg_min[node] = {val,pos};
        seg_max[node] = {val,pos};
        return;
    }

    ll mid = (s+e)>>1;
    if(pos <= mid) update(2*node,s,mid,pos,val);
    else update(2*node+1,mid+1,e,pos,val);

    seg_max[node] = max(seg_max[2*node],seg_max[2*node+1]);
    seg_min[node] = min(seg_min[2*node],seg_min[2*node+1]);
}

pair<ll,ll> query_min(ll node,ll s,ll e,ll qs,ll qe){
    if(s > e || qs > e || qe < s) return {1e10,0};

    if(qs <= s && e <= qe){
        return seg_min[node];
    }

    ll mid = (s+e)>>1;
    return min(query_min(2*node,s,mid,qs,qe),query_min(2*node+1,mid+1,e,qs,qe));
}

pair<ll,ll> query_max(ll node,ll s,ll e,ll qs,ll qe){
    if(s > e || qs > e || qe < s) return {0,0};

    if(qs <= s && e <= qe){
        return seg_max[node];
    }

    ll mid = (s+e)>>1;
    return max(query_max(2*node,s,mid,qs,qe),query_max(2*node+1,mid+1,e,qs,qe));
}