Segment tree doesn't take care of all segments of input data. Is there an efficient date structure that does?

Question

Segment tree is an efficient, but not always completely useful date structure. For example: if we have an array of length 8, it will take care of segments 1-2, 3-4, 5-6, 7-8, 1-4, 5-8 and 1-8. But many will be left out, such as 2-3, 2-4, 4-5, 6-7 etc. Is there an efficient data structure that takes care of all of the segments of input data?

Answer 1

No, its not true. It actually "take care" of every intervals.

For instance, in above segment tree, if you need to perform an query for range [4, 7], it will go to left subtree like [0, 4] -> [3, 4] -> [4, 4] and in right subtree [5, 9] -> [5, 7] and then aggregate the result of [4, 4] and [5, 7] and pass the result up to root.

I would suggest to simulate with pen and paper or use your debugger to see what happens under the hood of the recursion calls. Good luck!