A Fenwick tree <https://en.wikipedia.org/wiki/Fenwick_tree> is a table of
size N that encodes an array of N values and can be used to support the
following operations in O(log N) time:

   - Return the sum of any given contiguous subsequence of the array,
   - Change the value of a given array element to a given new value,
   - If all array elements are nonnegative, determine the shortest prefix
   of the array whose sum is at least a given value.

Have you used Fenwick trees for real applications (i.e. not online coding
challenges and the like)? Would you be interested in seeing them added to
the standard library?

(In general, the values represented by a Fenwick tree don't have to be
numbers, but can be members of any abelian group. So while the
implementation is easy, the design is not so easy: we don't have anything
in the standard library yet that is generic with respect to an abelian
group, and we don't have the concepts for it yet.)

-- 
*Brian Bi*