Segment and Fenwick trees

A segment tree is a structure for answering questions about ranges of an array, like “what’s the sum (or minimum) of items 30 through 900?”, while the array keeps changing. It builds a tree where the root summarizes the whole array, its two children summarize each half, and so on down to single items. Any range can be covered by a handful of these precomputed pieces, so both queries and updates touch only about log n nodes instead of scanning the range. A Fenwick tree, or binary indexed tree, is a smaller, simpler cousin that uses the binary digits of each index to decide which range it stores; it works well for sums but not for things like minimum.