I don't think segment trees are a good candidate for standardization. There
are multiple different implementation strategies and the choice of
implementation strategy affects performance in a meaningful way. Past
experience suggests that in such cases, the standard library implementation
ends up being unusable for a significant fraction of C++ users, and even if
there's a way to change the standard library implementation such that the
vast majority of users are better off and the negative effect on the
remainder is relatively insignificant, it won't be done because of ABI
compatibility.

With Fenwick trees, those concerns are not present. All implementations are
essentially the same except for whether they use a 0-based or 1-based
array, which doesn't impact performance in any significant way.

On Thu, Oct 15, 2026 at 11:31 AM Ivan Lazaric <ivan.lazaric1_at_[hidden]>
wrote:

> 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
>>
>

-- 
*Brian Bi*