Untitled

template <class T> class SparseTable { // 0-indexed
public:
    T (*funcOp)(T, T); 
    int n;
    vector<vector<T>> st;
    
    SparseTable() {}

    SparseTable(vector<T> v, T (*inputOp)(T, T)) {
        n = v.size();
        st = vector<vector<T>>(__lg(n)+1, vector<T>(n));
        st[0] = v;
        this->funcOp = inputOp;
        for (int i=1; i<st.size(); i++) {
            for (int j=0; j+(1<<i)<=n; j++) st[i][j] = funcOp(st[i-1][j], st[i-1][j+(1<<(i-1))]);
        }
    } 
    
    // Can't be used for sum operations. 
    T Query(int L, int R) { // inclusive range
        int sz = __lg(R - L +1);
        return funcOp(st[sz][L], st[sz][R-(1<<sz)+1]);
    }

    T QuerySum(int L, int R) {
        long long sum = 0;
        for (int i = st.size() - 1; i >= 0; i--) 
        {
            if ((1 << i) <= R - L + 1) {
                    sum += st[i][L];
                    L += 1 << i;
            }
        }
        return sum;
    }
};

int AND(int a, int b) {
            return a & b;
}

int MIN(int a, int b) {
            return min(a, b);
}


class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        int n = nums.size();
        auto stAnd = SparseTable<int>(nums, AND);        
        
        int res = 0;
        int minVal = INT_MAX;
        for (int i = 0; i < n; ++i)
        {
            int lo = i;
            int hi = n - 1;
            while (lo < hi)
            {
                int mid = lo + (hi - lo + 1) / 2;
                
                int val = stAnd.Query(i, mid);
                if (val >= k) lo = mid;
                else hi = mid - 1;
            }
            
            int val = abs(stAnd.Query(i, lo) - k);
            if (val < minVal)
            {
                minVal = val;                
            }
            if (lo + 1 < n)
            {
                int val = abs(stAnd.Query(i, lo + 1) - k);
                if (val < minVal)
                {
                    minVal = val;                
                }   
            }
        }
        
        return minVal;
    }
};