Fenwick Tree
A Fenwick Tree, also known as a Binary Indexed Tree, is a data structure that efficiently supports dynamic cumulative frequency tables. It allows for quick updates and prefix sum queries, making it useful in scenarios where you need to calculate the sum of elements in a range or update individual elements frequently.
The structure is built using an array, where each index stores information that helps compute sums of elements in logarithmic time. This efficiency makes the Fenwick Tree a popular choice in competitive programming and algorithm design, particularly for problems involving range queries and updates.