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.
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.