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