Fenwick Tree

Consider the following problem: You are given a list of $N$ integers $A_1, A_2, \ldots, A_N$. Your task is to support the following two kinds of queries:

Note that you have no control over what operations will be done to your array, so your data structure must be able to handle any kind of sequence of operations without additional assumptions.

There are some very simple ways to implement it. One way would be to simply maintain an array of integers $A[1\ldots N]$ and do the operations as requested. However, this runs very slowly. Specifically, each Sum query runs in $O(N)$ time in the worst case, so performing $Q$ operations takes $O(QN)$ time.

A Fenwick tree is a data structure that can perform these operations each in $O(\log N)$, so performing $Q$ of them takes $O(Q \log N)$ time in the worst case, which is much better than $O(QN)$ (and is usually good enough for most practical purposes).

One of the best tutorials I found that introduces and explains Fenwick trees can be found in TopCoder tutorials. We recommend reading it.