[qwerty3344]

rope - https://en.wikipedia.org/wiki/Rope_%28data_structure%29 skip list - https://en.wikipedia.org/wiki/Skip_list

[2OEH8eoCRo0]

Never heard of this one until it came up in a google interview. Totally botched it. I couldn't think of any way to do it to their liking that doesn't require a dynamic cast.