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.
 avatar
unknown
plain_text
a month ago
2.3 kB
1
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);
        }

    }

}
Leave a Comment