For the range [a,b] if we have pre-calculated (b-a)^(1/3) distinguished points, we would need only (b-a)^(1/3) group operations in order to find the collision. But precomputation requires (b-a)^(2/3) group operations (performed once as a preliminary stage).
If you can store (b-a)^2/3 distinguished points,
the best things to do is to generate 1*G, 2*G, 3*G, ...., (b-a)^2/3 * G.
In this way you can use the BSGS algorithm, that is faster than kangaroo (less steps - on average 2^(N/2) - and each step is faster because the points are consecutive)
For each public key P, if you try with these (b-a)^1/3 giant steps:
P-
1*(b-a)^2/3*G, P-
2*(b-a)^2/3*G, P-
3*(b-a)^2/3*G, ..., P -
(b-a)^1/3*(b-a)^2/3*G = P - (b-a)*G you will recover for sure the private key (on average in 0.5*(b-a)^(1/3) steps).
You have divided the interval into (b-a)^1/3 sub-intervals each with length = (b-a)^2/3
In case you have to find a key in a 45-bit space, you can shift the interval in [-(b-a)/2, (b-a)/2] and use only half baby steps (1*G, ..., 2^29*G) instead of 2^30 steps. And you need on average 2^14 steps to recover the key. Then in a space of 2^n points you need only 2^((n/3)-1) steps (if you have precomputed 2^((2*n/3)-1) points)
In case you have to find a key in a 90-bit space and you have only 2^29 precomputed points, you need no more than 2^60 giant steps (2^60 sub-intervals to search through) to find a key, on average 2^59 giant steps. Then much better kangaroo.
In any case for large space (like 90 bits), (b-a)^(2/3) means 2^60, too much.
If you want to find many public keys in 69 bits, you need to store 2^46 points, too much.
If you want to find many public keys in 2^45 bits, you need to store 2^30 points, ok, you have enough space to store them. But finding public keys in 2^23 steps or in 2^15 is similar, it takes less than 1 sec for each key. Unless you need to find millions of public keys, there is no difference.
