Segment tree template

 avatar
unknown
plain_text
4 years ago
1.8 kB
14
Indexable
https://cses.fi/problemset/task/1648
https://cses.fi/problemset/task/1649/

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int mini;
};
Node merge(const Node& l, const Node& r) {
    Node merged;
    merged.mini = min(l.mini, r.mini);
    return merged;
}
const int N = 2e5 + 10;
Node tree[4 * N];
int pos[N], a[N];
void build(int root, int node_l, int node_r){
    if(node_l == node_r){
        tree[root].mini = a[node_l];
        pos[node_l] = root;
        return;
    }
    int mid = (node_l + node_r) >> 1;
    build(2 * root, node_l, mid);
    build(2 * root + 1, mid + 1, node_r);
    tree[root] = merge(tree[2 * root], tree[2 * root + 1]);
}
Node query(int root, int node_l, int node_r, int query_l, int query_r){
    int mid = (node_l + node_r) >> 1;
    if(query_l <= node_l && query_r >= node_r) {
        return tree[root];
    } else if(query_r <= mid) {
        return query(2 * root, node_l, mid, query_l, query_r);
    } else if(query_l > mid) {
        return query(2 * root + 1, mid + 1, node_r, query_l, query_r);
    } else {
        return merge(query(2 * root, node_l, mid, query_l, query_r), query(2 * root + 1, mid + 1, node_r, query_l, query_r));
    }
}
void update(int index, int val){
    int root = pos[index];
    tree[root].mini = val;
    root >>= 1;
    while(root > 0){
        tree[root] = merge(tree[2 * root], tree[2 * root + 1]);
        root >>= 1;
    }
}
int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        scanf("%d", a + i);
    }
    build(1, 0, n - 1);
    for (int i = 0; i < q; i++) {
        int type, x, y;
        scanf("%d %d %d", &type, &x, &y);
        if (type == 1) {
            x--;
            update(x, y);
        } else {
            x--, y--;
            printf("%d\n", query(1, 0, n - 1, x, y).mini);
        }
    }
}
Editor is loading...