rmq_twod_stable.sublime-snippet

<snippet>
	<content><![CDATA[
// arr is the array on which sparse table is built
// O(n*m*log(n)*log(m))
// can built for n*m upto 1e6
// used int to prevent overflow by 1000*1000*11*11 space matrix
void twod_sparsetable(int n,int m)
{
    for(int ir=0;ir<n;ir++)
    {
        for(int ic=0;ic<m;ic++)
            table[0][ir][0][ic]=arr[ir][ic];
       
        for(int jc=1;jc<=log2(m);jc++)
            for(int ic=0;ic+me(2,(jc-1))<m;ic++)
                table[0][ir][jc][ic]=max(table[0][ir][jc-1][ic],table[0][ir][jc-1][ic+me(2,(jc-1))]);
    }  
    for(int jr=1;jr<=log2(n);jr++)
        for(int ir=0;ir<n;ir++)
            for(int jc=0;jc<=log2(m);jc++)
                for(int ic=0;ic<m;ic++)
                    table[jr][ir][jc][ic]=max(table[jr-1][ir][jc][ic],table[jr-1][ir+me(2,(jr-1))][jc][ic]);
}


// 0 based indexing
// O(1) query time
int query(int x1,int y1,int x2,int y2)
{
    int lenx=x2-x1+1;
    int kx=log2(lenx);
    int leny=y2-y1+1;
    int ky=log2(leny);
    int min_R1=max(table[kx][x1][ky][y1],table[kx][x1][ky][y2+1-me(2,ky)]);
    int min_R2=max(table[kx][x2+1-me(2,kx)][ky][y1],table[kx][x2+1-me(2,kx)][ky][y2+1-me(2,ky)]);
    return max (min_R1,min_R2);
}
]]></content>
	<!-- Optional: Set a tabTrigger to define how to trigger the snippet -->
	<tabTrigger>rmq_twod_stable</tabTrigger>
	<!-- Optional: Set a scope to limit where the snippet will trigger -->
	<!-- <scope>source.python</scope> -->
</snippet>