Minimum Segment Tree

segment_tree.cpp

int next_binary_power(int x) {
    return 1 << (32 - __builtin_clz(x - 1));
}

struct SegmentTree {
    vector<int> nodes;

    SegmentTree(int size) : nodes(next_binary_power(size) * 2, INT_MAX) {}

    int query(int left, int right) {
        return query(1, 0, nodes.size() / 2, left, right);
    }

    int query(int node, int c_left, int c_right, int left, int right) {
        if (c_left >= right || c_right <= left) return INT_MAX;
        if (left <= c_left && c_right <= right) return nodes[node];
        int middle = (c_left + c_right) / 2;
        return min(query(node * 2, c_left, middle, left, right),
                query(node * 2 + 1, middle, c_right, left, right));
    }

    void update(int node, int c_left, int c_right, int index, int value) {
        if (c_left > index || c_right <= index) return;
        if (c_left == index && index + 1 == c_right) {
            nodes[node] = value;
            return;
        }

        int middle = (c_left + c_right) / 2;
        update(node * 2, c_left, middle, index, value);
        update(node * 2 + 1, middle, c_right, index, value);
        nodes[node] = min(nodes[node * 2], nodes[node * 2 + 1]);
    }
};