Answers for "cpp sparse table"

cpp sparse table

template<class T> struct SparseTable {

    T (*op)(T, T);
    vector<int> log2s;
    vector<vector<T>> table;

    SparseTable (const vector<T>& arr, T (*op)(T, T))
        : op(op) {
        // Preprocess the log 2s
        log2s = vector<int>(log2(arr.size())+2);
        for (int i = 2; i<log2s.size(); ++i) {
            log2s[i] = log2s[i/2]+1;
        }

        // Copy input over to the table
        table = vector<vector<T>>(arr.size(), vector<T>(log2s.size()));
        for (int i = 0; i<arr.size(); ++i) {
            table[i][0] = arr[i];
        }

        for (int power = 1; power < log2s.size(); ++power) {
            int prevPower = power - 1;
            for (int i = 0; i+(1<<power) <= table.size(); ++i) {
                table[i][power] = op(table[i][prevPower], table[i+(1<<prevPower)][prevPower]);
            }
        }
    }

    T query (int l, int r) {
        int power = log2s[r-l+1];
        return op(table[l][power], table[r-(1<<power)+1][power]);
    }

};