79368117

Date: 2025-01-18 23:21:55
Score: 2
Natty:
Report link

The truth is that a Fenwick tree can be seen, in a certain sense, as a "half" of a segment tree. Specifically, assume n is a power of two, then a segment tree's segments will always divide evenly into powers of two down to the last level as illustrated below: A segment tree with 64 length-1 leaves

This is how various segments are split by such a tree: Various falling segments split by a segment tree

Note that if a segment starts at zero, we will only use the blue segments, which are the left children in the segment tree: Segment tree splits for zero-touching segments

Since computing sums on intervals [l, r) can be reduced to computing prefix sums (for intervals starting at zero), we can limit ourselves to keeping just the blue segments. Additionally, each blue segment can be uniquely associated with the position of its right-hand side, and the specific layout provided by n being a power of two allows for a direct computation of the segment beginning given its end. That's where the previous segment in the split starts, so we get an explicit way to enumerate constituent segments. Thus we get a Fenwick tree: A Fenwick tree

New questions arise:

For these, I refer you to this blog post.

Reasons:
  • Blacklisted phrase (1): this blog
  • Long answer (-1):
  • No code block (0.5):
  • Contains question mark (0.5):
  • Low reputation (1):
Posted by: Yury Kartynnik