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?
No, and 100% definitely not, respectively.
It does sound like an interesting data structure, which would be fun to implement in an STL-style way and make available on GitHub or wherever. Such a library does not belong in the International Standard.
I'd be interested in seeing such an implementation. At a quick glance it sounds like one of those "not-really-STL-style"
data structures, like a suffix tree or
sg14::slot_map, that has some interesting questions re: how much it should, or can, really resemble an STL
container.
–Arthur