Are you sure the naive approach is too slow? Have you Benchmarked it?

Sure, splice is O(n), but if n=1000 that's still pretty fast! Implement it in C if you want, but I'm not sure you'll gain much. I think a tree is likely to be overkill here.

-sam