This is the C++ source code for the paper:

• Daniel Lemire and Owen Kaser, Hierarchical Bin Buffering: Online Local Moments for Dynamic External Memory Arrays http://arxiv.org/abs/cs.DS/0610128

This paper includes a survey as well as new methods to precompute polynomial range queries, as they are used in polynomial curve fitting and statistics.

Code sample:

  OlaBuffer<float> ob(2,1); // this is the object which computes the buffers
  counted_ptr<vector<float> > buffer = ob.computeBuffer(data);// buffers the vector "data"
  // we define a query
  int begin = 0, end =5;
  RangedCubicPolynomial rcp (1,0,0,0,begin,end);  
  // we execute the query (very fast):
  float fastway = ob.query(rcp,data,*buffer);

For a starting point, see the file dubuc/benchmark.cpp

Examples of queries that can be written as polynomial range queries include: the sum of the array between index i and index j, the center of mass of the array between the index i and the index j, and so on.