For \(2^k<T<2^{k+1}\) , one can similarly define \(S_i=\lbrace [1,2^i],[2^i+1,2^{i+1}],...,[2^i \lfloor \frac{T-1}{2^i}\rfloor +1,T]\rbrace \) , see [1]}. Hencefore at any time \(\tau \)  the number of 'active' intervals is only \(O(\log (T))\) , this guarantees that the running time and memory cost per round of SAMUEL is as fast as \(O(\log (T))\) .
