セグメントツリーメモ
更新は再帰的に処理します。各操作O(logN)
///RMQ #define SIZE (1<<18) #define ll long long #define INF (1<<30)///必要に応じて増やす ll int MSEG[SIZE]; void update(int index){ if(index==0)return; int l = index*2,r = index*2+1,tmp = MSEG[index]; if(MSEG[l]<MSEG[r]){ MSEG[index] = MSEG[l]; }else{ MSEG[index] = MSEG[r]; } if(tmp==MSEG[index])return;///更新が無ければ終了 update(index/2); } ll getMin(int a,int b,int k,int l,int r){ if(b<l||a>r)return INF;///含まない if(a<=l&&r<=b)return MSEG[k];///[a,b]が[l,r]を完全に含む ll ml = getMin(a,b,k*2,l,(r-l)/2+l);///左側 ll mr = getMin(a,b,k*2+1,(r-l)/2+l+1,r);///右側 return min(ml,mr); }