Segment Tree Implementation in C++
This snippet demonstrates a segment tree implementation in C++. It includes logic for building the tree, pushing updates to children, and querying for minimum values over a range. Using techniques like lazy propagation, it efficiently manages updates and queries for large datasets.unknown
plain_text
10 months ago
2.3 kB
3
Indexable
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 7;
const int INF = 1e9 + 7;
int t[4 * MAXN], add[4 * MAXN];
void push(int v, int tl, int tr){
if (add[v] != 0 && tl < tr){
// tm = (tl + tr) / 2;
t[v + v] += add[v];
//t[v + v] += add[v] * (tm - tl + 1);
t[v + v + 1] += add[v];
//t[v + v + 1] += add[v] * (tr - tm);
add[v + v] += add[v];
add[v + v + 1] += add[v];
add[v] = 0;
}
}
void build(int v, int tl, int tr){
if (tl > tr)
return;
if (tl == tr){
t[v] = a[tl];
return;
}
int tm = (tl + tr) / 2;
build(v + v, tl, tm);
build(v + v + 1, tm + 1, tr);
t[v] = min(t[v + v], t[v + v + 1]);
}
int get_min(int v, int tl, int tr, int l, int r){
if (l > r){
return INF;
}
if (l == tl && r == tr){
return t[v];
}
push(v, tl, tr);
int tm = (tl + tr) / 2;
return min(get_min(v + v, tl, tm, l, min(r, tm)),
get_min(v + v + 1, tm + 1, tr, max(tm + !, l), r));
}
void update(int v, int tl, int tr, int pos, int val){
if (tl > tr)
return;
if (tl == tr){
t[v] = val;
return;
}
push(v, tl, tr);
int tm = (tl + tr) / 2;
if (pos <= tm)
update(v + v, tl, tm, pos, val);
else
update(v + v + 1, tm + 1, tr, pos, val);
t[v] = min(t[v + v], t[v + v + 1]);
}
void update2(int v, int tl, int tr, int l, int r, int val){
if (l > r)
return;
if (tl == l && r == tr){
t[v] += val;
// t[v] += val * (tr - tl + 1);
add[v] += val;
return;
}
push(v, tl, tr);
int tm = (tl + tr) / 2;
update2(v + v, tl, tm, l, min(r, tm), val);
update2(v + v + 1, tm + 1, tr, max(l, tm + 1), r, val);
t[v] = min(t[v + v], t[v + v + 1]);
}
int main(){
...
build(1, 1, n);
cin >> q;
while(q--){
cin >> type;
if (type == 1){
int l, r;
cin >> l >> r;
cout << get_min(1, 1, n, l, r) << '\n';
}
else {
int pos, val;
cin >> pos >> val;
update(1, 1, n, pos, val);
}
}
}
Editor is loading...
Leave a Comment