You are right, if you mean the cost of construction of an advanced data structure, it is O(N log N). As soon as the required data have been written the sum and mean value of any consecutive elements can be found in O(log N) time. Please, have a look at performance tests of the fast algorithm accumulate() in the section:
The next solution works in O(1) and requires only O(N) for construction step: template <typename T> class accumulator { public: void init(std::vector<T> &elems) { sum.reserve(elems.size() + 1); sum.push_back(0); for (std::vector<T>::iterator it = elems.begin(); it != elems.end(); ++it) { sum.push_back(sum.back() + *it); } } T operator()(T first, T last) const { return sum[last+1] - sum[first]; } private: std::vector<T> sum; }; I guess this solution is slightly better for those math targets you mentioned above. It also works with any associative operation. Andrii On Thu, Dec 1, 2011 at 11:42 AM, Thorsten Ottosen < thorsten.ottosen@dezide.com> wrote:
Den 30-11-2011 10:58, Vadim Stadnik skrev:
Hi all,
Advanced data structures (ADS) offer useful STL extensions that are not possible or not efficient with basic data structures, such as arrays, linked lists and red-black trees.
I'm interested. In particular, if the library can be integrated seamlessly with Boost.Accumulators and other libs, it seems very interesting.
Are there variations of the trees that allow for other types of fast queries than just accumulate? If so, then there might be a generic way to incorporate them.
-Thorsten
______________________________**_________________ Unsubscribe & other changes: http://lists.boost.org/** mailman/listinfo.cgi/boost<http://lists.boost.org/mailman/listinfo.cgi/boost>