Segment tree template
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...