Sparse Table

table[j][i] = answer for range [i, i + 2^j - 1]

For array: [5, 2, 8, 1, 9, 3, 7, 4]

table[0]: [5, 2, 8, 1, 9, 3, 7, 4]  // length 1
table[1]: [2, 2, 1, 1, 3, 3, 4, -]  // length 2
table[2]: [1, 1, 1, 1, 3, -, -, -]  // length 4
table[3]: [1, 1, -, -, -, -, -, -]  // length 8

// For query [2, 6] with min operation:
// Length = 5, so k = 2 (largest power: 2^2 = 4)

Range 1: [2, 5]  // table[2][2]
Range 2: [3, 6]  // table[2][6-4+1]

// Element 3, 4, 5 are in both ranges
// min(min(2,5), min(3,6)) = correct answer
// This works because min(x, x) = x (idempotent)

vector<int> values = {5, 2, 8, 1, 9, 3, 7, 4};

// Track both min and max
SparseTMin<int> st_min(values);
SparseTMax<int> st_max(values);

// Find range with smallest difference between min and max
int best_l = 0, best_r = 0;
int min_diff = INT_MAX;

for (int l = 0; l < values.size(); l++) {
    for (int r = l; r < values.size(); r++) {
        int mn = st_min.query(l, r);
        int mx = st_max.query(l, r);
        int diff = mx - mn;
        if (diff < min_diff) {
            min_diff = diff;
            best_l = l;
            best_r = r;
        }
    }
}

// Convert LCA problem to RMQ problem using Euler tour
vector<int> euler_tour;  // Nodes visited in DFS
vector<int> depth;       // Depth of each node in tour
vector<int> first_occurrence;  // First occurrence of each node

// Build sparse table on depths
SparseTMin<int> st(depth);

// Query LCA of nodes u and v
auto lca = [&](int u, int v) {
    int l = first_occurrence[u];
    int r = first_occurrence[v];
    if (l > r) swap(l, r);
    
    int min_depth_idx = st.query(l, r);
    return euler_tour[min_depth_idx];
};

vector<int> log_table(n + 1);
log_table[1] = 0;
for (int i = 2; i <= n; i++) {
    log_table[i] = log_table[i / 2] + 1;
}

// Use in query
T query(int l, int r) {
    int lg = log_table[r - l + 1];
    return func(table[lg][l], table[lg][r - (1 << lg) + 1]);
}

// Only store needed levels
template <typename T, typename Operate>
class CompactSparseTable {
    vector<T> data;
    Operate func;
    int n, levels;
    
    int index(int level, int pos) {
        return (n - (1 << level) + 1) * level + pos;
    }
    
public:
    CompactSparseTable(const vector<T> &v) {
        n = v.size();
        levels = 32 - __builtin_clz(n);
        
        int total_size = 0;
        for (int i = 0; i < levels; i++) {
            total_size += n - (1 << i) + 1;
        }
        data.resize(total_size);
        
        // Build table
        for (int i = 0; i < n; i++) data[i] = v[i];
        
        int offset = n;
        for (int j = 1; j < levels; j++) {
            int len = 1 << j;
            for (int i = 0; i <= n - len; i++) {
                data[offset + i] = func(
                    data[offset - (n - len / 2 + 1) + i],
                    data[offset - (n - len / 2 + 1) + i + len / 2]
                );
            }
            offset += n - len + 1;
        }
    }
};