Answers for "sparse table c++"

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]);
    }

};

2d sparse table c++

#define vec vector

struct SparseTable2D {

    vec<int> log2s;
    vec<vec<vec<vec<int>>>> table;

    SparseTable2D () = default;

    explicit SparseTable2D (const vec<vec<int>>& arr) {
        // Preprocess the log 2s
        log2s = vec<int>(max(arr.size(), arr[0].size())+1);
        for (int i = 2; i<log2s.size(); ++i) {
            log2s[i] = log2s[i/2]+1;
        }

        // Copy input over to the table
        table = vec<vec<vec<vec<int>>>>(
                (int) log2(arr.size())+1, vec<vec<vec<int>>>(
                        arr.size(), vec<vec<int>>(
                                (int) log2(arr[0].size())+1, vec<int>(
                                        arr[0].size()
                                        ))));
        for (int i = 0; i<arr.size(); ++i) {
            for (int j = 0; j<arr[0].size(); ++j) {
                table[0][i][0][j] = arr[i][j];
            }
            // Create each 1D sparse table
            auto& cur = table[0][i];
            for (int power = 1; power<cur.size(); ++power) {
                int prevPower = power-1;
                for (int j = 0; j+(1<<power)<=cur[0].size(); ++j) {
                    cur[power][j] = min(cur[prevPower][j], cur[prevPower][j+(1<<prevPower)]);
                }
            }
        }

        for (int iPower = 1; iPower<table.size(); ++iPower) {
            int prevPower = iPower-1;
            for (int i = 0; i+(1<<iPower)<=table[0].size(); ++i) {
                for (int jPower = 0; jPower<table[0][0].size(); ++jPower) {
                    for (int j = 0; j<table[0][0][0].size(); ++j) {
                        // Find the minimum of the rectangle made at coord
                        // (i, j) with a height of iPower and width of jPower
                        // By taking the min of 1 previous rectangle at the
                        // same coords but half the height and same width
                        // and the rectangle with the same dimensions directly
                        // below it.
                        table[iPower][i][jPower][j] = min(table[prevPower][i][jPower][j],
                                                          table[prevPower][i+(1<<prevPower)][jPower][j]);
                    }
                }
            }
        }
    }

    int query (int u, int d, int l, int r) {
        int powerY = log2s[d-u+1];
        int powerX = log2s[r-l+1];
        int lenY = (1<<powerY)-1;
        int lenX = (1<<powerX)-1;
        int minRow1 = min(table[powerY][u][powerX][l], table[powerY][u][powerX][r-lenX]);
        int minRow2 = min(table[powerY][d-lenY][powerX][l], table[powerY][d-lenY][powerX][r-lenX]);

        return min(minRow1, minRow2);
    }

};