Im writing this both to help others and test myself so I will try to explain everything at a basic level.

A Fenwick Tree (a.k.a Binary Indexed Tree, or BIT) is a fairly common data structure. BITs are used to efficiently answer certain types of range queries, on ranges from a root to some distant node. They also allow quick updates on individual data points.

An example of a range query would be this: "What is the sum of the numbers indexed from [0,x]?"

An example of an update would be this: "Increase the number indexed by x by v."

A BIT can perform both of these operations in O(log N) time, and takes O(N) memory.

So how does this work?

BITs take advantage of the fact that ranges can be broken down into other ranges, and combined quickly. Adding the numbers 1 through 4 to the numbers 5 through 8 is the same as adding the numbers 1 through 8. Basically, if we can precalculate the range query for a certain subset of ranges, we can quickly combine them to answer any [0,x] range query.

The binary number system helps us here. Every number N can be represented in log N digits in binary. We can use these digits to construct a tree like so:

/predownloaded/d7/d3/d7d3bf975dd3a747ab44ca1945f534aa45f1c435.png