Segment tree template

unknown
plain_text
3 years ago
1.8 kB
7
Indexable
Never
```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);
}
}
}
```