# Computationally and memory efficient algorithm for a relatively simple problem

Given a list of non-overlapping ranges and values, i.e. [(0, 5, 0.5), (10, 15, 1.1), ...], and a list of potentially overlapping ranges (bins), i.e. [(0, 10), (5, 15), (0, 5), ...], find the average, min, max, standard deviation of the bins.

For example, the answer for averages would be [0.25, 0.55, 0.5, ...]. Assume there is a implicit range (5, 10, 0) in the first list.

The max range is from 1 to 109. The number of bins ranges from 1 $$\le$$ n $$\ge$$ 1010.

What is a memory and computationally efficient way of solving this problem?

Edit: The first list of non-overlapping ranges would create a list: [0.5, 0.5, 0.5, 0.5, 0.5, 0, 0, 0, 0, 0, 1.1, 1.1, 1.1, 1.1, 1.1, ...]. A pair in the second list would specify the indices of the range to find a statistic. The average for the first pair, (0, 10), would be (0.5 * 5 + 0 * 5) / 10 = 0.25.

This is an actual problem in bioinformatics, and an algorithm already exists here, but I was wondering if there was a potentially better one.

• Welcome to COMPUTER SCIENCE @SE. If this problem is from a third party, please see the help for proper referencing. (The comparison operators look off.) Mar 8 at 17:37
• I suppose this is from some competition, so asking people for help completely misses the point. The way to improve your ability to solve such problems is to solve them or try to solve them. Mar 8 at 21:24
• What is the std of a bin? Mar 8 at 21:25
• Which numbers exactly are represented for example by (0, 10, 0.5) ? I think if you had tried to solve this problem just a little bit, your question would have stated things much more precisely. Mar 8 at 21:26
• There is no $n$ smaller than or equal to one and greater than or equal to $10^9$. Mar 9 at 23:08

I don't know what algorithm they use so I don't know whether this will be better, but there is an efficient algorithm for your problem, by using a tree. Form the list of all endpoints of all ranges and bins, and sort it. This partitions the real line into non-overlapping intervals, where each bin is a union of intervals that don't overlap.

Put those endpoints into a binary search tree. Each internal node in the binary tree represents a union of those intervals. You can store, in each tree, the min, max, sum, and sum of squares of all values in that interval, filling these in bottom-up. Note that given these statistics for the two children of a node, it is easy to compute these statistics for the node itself in $$O(1)$$ time.

This yields an $$O(n \log n)$$ time algorithm, where $$n$$ counts the number of ranges + number of bins. It takes $$O(n \log n)$$ time to sort the endpoints, then $$O(n)$$ time to build the binary search tree, then $$O(n)$$ time to fill in each node bottom-up.

You might also enjoy reading about interval trees and segment trees, if you do a lot of computation on ranges/intervals.