Four Russian RMQ算法的C++实现

Four Russian RMQ算法的基本思想是对原序列分块对每块及块间均建立ST表从而处理块内和块间查询具体见以下代码C代码:#includeiostream#includevector#includerandomusingnamespacestd;size_tlog2(size_t N){size_t k0;while(1ullkN){k;}--k;returnk;}templatetypenameTstructm_info{T m_value;size_t index;m_info(constTm,size_t i):m_value(m),index(i){}m_info()default;booloperator(constm_infobe_compared)const{returnm_valuebe_compared.m_valueindexbe_compared.index;}};templatetypenameTconstm_infoTmin_m_info(constm_infoTleft,constm_infoTright){if(left.m_valueright.m_value){returnleft;}returnright;}templatetypenameTvoidSparseTable(vectorvectorm_infoTd,vectorTseq,size_t left,size_t right)//[left, right]从0开始{for(size_t i0;iright-left;i){d[i][0]m_infoT(seq[ileft],i);}for(size_t i1;(1i)right-left1;i){for(size_t j0;jright-left1-(1i);j){if(d[j][i-1].m_valued[j(1i-1)][i-1].m_value){d[j][i]d[j][i-1];}else{d[j][i]d[j(1i-1)][i-1];}}}}templatetypenameTm_infoTquery(size_t i,size_t j,vectorvectorm_infoTd)//i,j从0开始算{size_t lj-i1;size_t klog2(l);if(d[i][k].m_valued[j-(1k)1][k].m_value)returnd[i][k];returnd[j-(1k)1][k];}templatetypenameTclassFourRussianRMQ{public:m_infoTqueryRMQ(size_t i,size_t j);FourRussianRMQ(vectorTv,size_t s,constTm);private:T max_value_for_type;size_t N;size_t segment_length;size_t block_num;vectorTvalue_seq;vectorvectorvectorm_infoTgroup_in_query_map_table;vectorvectorm_infoTgroup_between_query_table;vectorvectorm_infoTprefix_RMQ;vectorvectorm_infoTsuffix_RMQ;voidpreProcess();};templatetypenameTm_infoTFourRussianRMQT::queryRMQ(size_t i,size_t j){if(ij||jN){cout非法的查询索引!endl;exit(-1);}size_t i_block_indexi/segment_length;size_t i_in_block_indexi%segment_length;size_t j_block_indexj/segment_length;size_t j_in_block_indexj%segment_length;m_infoTresult;size_t first_value_in_block_offset;if(i_block_indexj_block_index){if(i_in_block_index0){resultprefix_RMQ[i_block_index][j_in_block_index];}elseif(j_in_block_indexsegment_length-1){resultsuffix_RMQ[i_block_index][i_in_block_index];}else{resultquery(i_in_block_index,j_in_block_index,group_in_query_map_table[i_block_index]);}first_value_in_block_offseti_block_index*segment_length;}else{if(i_in_block_index0j_in_block_indexsegment_length-1){resultquery(i_block_index,j_block_index,group_between_query_table);size_t block_indexresult.index;resultprefix_RMQ[block_index][segment_length-1];first_value_in_block_offsetblock_index*segment_length;}else{m_infoTr_ref;m_infoTresult2;m_infoTresult3;size_t block_index;if(i_block_index1j_block_index){result2suffix_RMQ[i_block_index][i_in_block_index];result3prefix_RMQ[j_block_index][j_in_block_index];r_refmin_m_info(result2,result3);}else{if(i_in_block_index0){resultquery(i_block_index,j_block_index-1,group_between_query_table);}elseif(j_in_block_indexsegment_length-1){resultquery(i_block_index1,j_block_index,group_between_query_table);}else{resultquery(i_block_index1,j_block_index-1,group_between_query_table);}block_indexresult.index;resultprefix_RMQ[block_index][segment_length-1];if(i_in_block_index0||j_in_block_indexsegment_length-1){if(i_in_block_index0){result2prefix_RMQ[j_block_index][j_in_block_index];}else{result2suffix_RMQ[i_block_index][i_in_block_index];}r_refmin_m_info(result,result2);}else{result2suffix_RMQ[i_block_index][i_in_block_index];result3prefix_RMQ[j_block_index][j_in_block_index];r_refmin_m_info(result,min_m_info(result2,result3));}}if(i_block_index1!j_block_indexr_refresult){first_value_in_block_offsetblock_index*segment_length;}else{if(i_block_index1j_block_indexr_refresult3||i_block_index1!j_block_index(i_in_block_index!0j_in_block_index!segment_length-1r_refresult3)){first_value_in_block_offsetj_block_index*segment_length;result3.indexfirst_value_in_block_offset;returnresult3;}else{if(i_block_index1!j_block_indexi_in_block_index0){first_value_in_block_offsetj_block_index*segment_length;}else{first_value_in_block_offseti_block_index*segment_length;}result2.indexfirst_value_in_block_offset;returnresult2;}}}}result.indexfirst_value_in_block_offset;returnresult;}templatetypenameTvoidFourRussianRMQT::preProcess(){vectorTm_value_for_every_block(block_num);size_t start_index_for_left_bound0;for(size_t i0;iblock_num;i){prefix_RMQ[i][0]m_infoT(value_seq[start_index_for_left_bound],0);for(size_t jstart_index_for_left_bound1;jstart_index_for_left_boundsegment_length;j){if(value_seq[j]prefix_RMQ[i][j-start_index_for_left_bound-1].m_value){prefix_RMQ[i][j-start_index_for_left_bound]m_infoT(value_seq[j],j-start_index_for_left_bound);}else{prefix_RMQ[i][j-start_index_for_left_bound]prefix_RMQ[i][j-start_index_for_left_bound-1];}}suffix_RMQ[i][segment_length-1]m_infoT(value_seq[start_index_for_left_boundsegment_length-1],segment_length-1);if(segment_length1){for(size_t jstart_index_for_left_boundsegment_length-2;;--j){if(value_seq[j]suffix_RMQ[i][j-start_index_for_left_bound1].m_value){suffix_RMQ[i][j-start_index_for_left_bound]m_infoT(value_seq[j],j-start_index_for_left_bound);}else{suffix_RMQ[i][j-start_index_for_left_bound]suffix_RMQ[i][j-start_index_for_left_bound1];}if(jstart_index_for_left_bound){break;}}}SparseTable(group_in_query_map_table[i],value_seq,start_index_for_left_bound,start_index_for_left_boundsegment_length-1);start_index_for_left_boundstart_index_for_left_boundsegment_length;m_value_for_every_block[i]query(0,segment_length-1,group_in_query_map_table[i]).m_value;}SparseTable(group_between_query_table,m_value_for_every_block,0,m_value_for_every_block.size()-1);}templatetypenameTFourRussianRMQT::FourRussianRMQ(vectorTv,size_t s,constTm):value_seq(v),N(v.size()),segment_length(s),block_num(N%segment_length!0?N/segment_length1:N/segment_length),group_in_query_map_table(block_num,vectorvectorm_infoT(segment_length,vectorm_infoT(log2(segment_length)1))),group_between_query_table(block_num,vectorm_infoT(log2(block_num)1)),prefix_RMQ(block_num,vectorm_infoT(segment_length)),suffix_RMQ(block_num,vectorm_infoT(segment_length)),max_value_for_type(m){if(value_seq.empty()){coutERROR输入序列为空!endl;exit(-1);}if(segment_lengthN){coutERROR分块长度应小于等于输入序列长度endl;exit(-1);}size_t r;if((rN%segment_length)!0){rsegment_length-r;for(size_t i1;ir;i){value_seq.push_back(m);}}preProcess();}intmain(){constintN256;vectorlonglongrmq_seq(N);for(size_t i0;iN;i){rmq_seq[i]i1;}shuffle(rmq_seq.begin(),rmq_seq.end(),default_random_engine());FourRussianRMQlonglongobj(rmq_seq,2,0xffffffffffffffffull1);for(size_t i0;irmq_seq.size()-1;i){for(size_t ji1;jrmq_seq.size();j){m_infolonglongrobj.queryRMQ(i,j);longlongmrmq_seq[i];for(size_t ki1;kj;k){if(rmq_seq[k]m){mrmq_seq[k];}}if(r.m_valuemrmq_seq[r.index]m){cout[i,j]查询结果正确!endl;}else{cout[i,j]查询结果错误!endl;exit(-1);}}}return0;}