SparseTable.sublime-snippet

<snippet>
	<content><![CDATA[
class SparseTable {
public:
    SparseTable(const vector<int>& array) {
        n = array.size();
        int maxLog = log2(n) + 1;
        st.assign(maxLog, vector<int>(n));
        buildSparseTable(array);
    }
    
    /*  Query : Returns minimum of Range (L- R) in O(1): 
        - Update the Operation accordigly.  */

    int query(int L, int R) {
        int j = log2(R - L + 1);
        return ${1:min}(st[j][L], st[j][R - (1 << j) + 1]); 
    }

private:
    int n;
    vector<vector<int>> st;

    void buildSparseTable(const vector<int>& array) {
        for (int i = 0; i < n; ++i) {
            st[0][i] = array[i];
        }

        for (int j = 1; (1 << j) <= n; ++j) {
            for (int i = 0; i + (1 << j) - 1 < n; ++i) {
                st[j][i] = ${1:min}(st[j-1][i], st[j-1][i + (1 << (j-1))]);
            }
        }
    }
};
]]></content>
	<!-- Optional: Set a tabTrigger to define how to trigger the snippet -->
	<tabTrigger>template-SparseTable() minQuery</tabTrigger>
	<!-- Optional: Set a scope to limit where the snippet will trigger -->
	<scope>source.c++</scope>
</snippet>