Fenwick

A Fenwick tree, or Binary Indexed Tree, is a data structure that efficiently manages prefix sums—cumulative totals—to quickly answer questions like "What is the sum of the first k numbers?" and update individual elements. It stores partial sums in a way that allows both updating values and retrieving sums in logarithmic time, making it ideal for situations where data changes frequently and fast calculations are needed. Think of it as a smart storage system that keeps track of sums in layers, enabling rapid calculations without recomputing everything from scratch each time.