Fenwick or segment tree for a shared metrics library — how do you decide, and what do you tell the team?

## The decision is not between two data structures When someone proposes adding a range-query structure to a shared library, the interesting judgment is upstream of the structure. Three questions, in this order. **1. What is the aggregate, and what will it be?** A prefix-based structure answers a general range by subtracting prefixes, which only works for invertible aggregates — sums, counts, XOR. A segment tree combines covering blocks and needs only associativity plus an identity, so it also serves minimum, maximum and gcd. If the roadmap has any chance of asking for "coldest reading in the window" or "peak concurrent value in the window", the compact option is already off the table and the rest of the analysis is moot. Choosing a structure whose ceiling you will hit in two quarters buys nothing. **2. What is the real update-to-query ratio?** This is a measurement, not a guess. Writes that arrive in scheduled batches, with reads in between, do not need either tree: rebuild a flat summary once per batch in O(n) and serve every read in O(1), with code any reviewer can verify at a glance. Only genuinely interleaved single-value updates and range reads justify paying O(log n) on the read path to make writes logarithmic. **3. What breaks at ten times the volume?** For these structures it is almost never asymptotics — it is memory and cardinality. One tree per counter series is fine for a hundred series and a problem for a hundred thousand; the per-series overhead (n words versus several times n, plus per-object overhead) is what hits a memory ceiling on a fleet. The scaling failure typically arrives as "we now keep one of these per tenant", not as "our queries got slower". ## What separates them once you are actually choosing | | Fenwick tree | segment tree | |---|---|---| | aggregates | invertible only | any associative combine, with identity | | native query | prefix; general range by subtraction | any range directly | | memory | about n words | roughly 2n–4n node slots | | code volume | two short loops | recursion or iterative walk, plus identity handling | | constants | very tight, cache-friendly | good, but heavier per step | | failure mode | silently wrong on a reversed bit direction | silently wrong on a wrong identity | Both are O(log n) for query and update, so asymptotics do not decide this; memory, generality and maintenance risk do. ## What you tell the team **Put an interface in front of it.** Two operations — update a position, query a range — with the aggregate as a parameter of the type. Callers should never touch the node array. That single decision converts "which structure" from an irreversible architectural commitment into a swappable implementation detail, and it is worth more than getting the initial choice right. **Ship the simplest thing that meets the budget.** If sums are the only requirement today and the interface is narrow, the compact structure is defensible precisely because replacing it later costs one file. If the requirement set is already broader, take the general structure now rather than maintaining two. **Mandate an oracle test.** Both structures fail silently: a reversed bit direction or a wrong identity element still returns plausible numbers, and both are correct on the easy cases — small indices, windows that start at the first position. The non-negotiable test is a randomised sequence of interleaved updates and queries compared against a brute-force scan. This costs an afternoon and is the only thing standing between the library and a class of bug that never throws. **Name the maintenance cost honestly.** A bit-trick loop that three people on the team can read is a real cost, not a style preference. If the structure is on the critical path of an on-call dashboard, the person paged at 3am must be able to reason about it. That argues for whichever version the team can actually review, plus a comment stating the invariant — node `i` covers the low-bit-many positions ending at `i`, or a node's value is the aggregate of its half of the range — since the code alone does not say it. ## The answer that fails this question The weak version picks a structure in the first sentence and defends it on asymptotics. Both are O(log n); saying so distinguishes nothing. The second-weakest version picks the more powerful structure reflexively "for flexibility" without asking whether any tree is needed at all — which is how a service with nightly batch loads ends up maintaining a tree, an invariant and an oracle test to serve reads that a single precomputed pass would have answered faster. The judgment being tested is whether you can talk yourself *out* of the interesting structure when the workload does not ask for it, and whether you can say what you would measure before anyone writes code.