I would strongly prefer segment trees over Fenwick.


On Thu, Oct 15, 2026 at 4:26 PM Brian Bi via Std-Proposals <
std-proposals_at_[hidden]> wrote:

> 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*
> --
> Std-Proposals mailing list
> Std-Proposals_at_[hidden]
> https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals
>