segment_tree.sa

// Segment Tree Implementation in C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class SegmentTree {
private:
    vector<int> tree;
    vector<int> arr;
    int n;

    void build(int start, int end, int node) {
        if (start == end) {
            tree[node] = arr[start];
        } else {
            int mid = (start + end) / 2;
            build(start, mid, 2 * node + 1);
            build(mid + 1, end, 2 * node + 2);
            tree[node] = min(tree[2 * node + 1], tree[2 * node + 2]);
        }
    }

    int query(int start, int end, int l, int r, int node) {
        if (r < start || end < l) {
            return INT_MAX;
        }
        
        if (l <= start && end <= r) {
            return tree[node];
        }
        
        int mid = (start + end) / 2;
        return min(query(start, mid, l, r, 2 * node + 1),
                   query(mid + 1, end, l, r, 2 * node + 2));
    }

    void update(int start, int end, int idx, int val, int node) {
        if (start == end) {
            arr[idx] = val;
            tree[node] = val;
        } else {
            int mid = (start + end) / 2;
            if (idx <= mid) {
                update(start, mid, idx, val, 2 * node + 1);
            } else {
                update(mid + 1, end, idx, val, 2 * node + 2);
            }
            tree[node] = min(tree[2 * node + 1], tree[2 * node + 2]);
        }
    }

public:
    SegmentTree(const vector<int>& input) {
        arr = input;
        n = arr.size();
        tree.resize(4 * n);
        build(0, n - 1, 0);
    }

    int query(int l, int r) {
        return query(0, n - 1, l, r, 0);
    }

    void update(int idx, int val) {
        update(0, n - 1, idx, val, 0);
    }

    void display() {
        cout << "Segment Tree: ";
        for (int i = 0; i < tree.size(); i++) {
            if (tree[i] != INT_MAX) {
                cout << tree[i] << " ";
            }
        }
        cout << endl;
    }
};

int main() {
    vector<int> arr = {1, 3, 2, 7, 9, 11};
    SegmentTree st(arr);
    
    st.display();
    
    cout << "Minimum in range [1, 4]: " << st.query(1, 4) << endl;
    cout << "Minimum in range [0, 5]: " << st.query(0, 5) << endl;
    cout << "Minimum in range [2, 3]: " << st.query(2, 3) << endl;
    
    st.update(2, 0);
    cout << "After updating index 2 to 0:" << endl;
    cout << "Minimum in range [1, 4]: " << st.query(1, 4) << endl;
    
    return 0;
}