This post is about memory requirements for fast range queries.

First, let's consider 2 following types of queries on a sequence x[0]..x[n-1] in O(logn):

• sum(a, b) — calculate x[a] + x[a+1] + ... + x[b]
• add(i, value) — x[i] += value

This is a well-known problem that can be solved using Fenwick tree.

What is good with Fenwick tree — is that it gives memory-optimal solution in the sense that it needs an array of only n elements, where each element has enough capacity to store any sum(a,b). Unlike Fenwick tree, any solution based on segment tree will use at least 2*n elements.

Now suppose we need range update and our query types become the following:

• sum(a, b) — calculate sum x[a] + x[a+1] + ... + x[b]
• add(a, b, value) — x[a]+=value x[a+1]+=value ... x[b]+=value

This is most often solved using segment tree with 2 arrays (something like sum[] and delta[]), each of 2*n or 4*n size. So the minimum memory consumption is 4*n which is far from optimal n.

We can improve. It was discovered that Fenwick tree can be altered to support both range queries and updates. All following solutions use 2*n elements:

• Petr blog: http://petr-mitrichev.blogspot.ru/2013/05/fenwick-tree-range-updates.html
• Topcoder forums: link1 link2
• habrahabr.ru (russian only): http://habrahabr.ru/post/170933/

However there is also a solution with segment tree that seems to work, but I don't have a prove. We leave only array sum[] and while walking down the tree we push delta = sum[i] — sum[2*i+1] — sum[2*i+2] down. He is source code, which is not quite honest though, because it achieves 2*n consumption only if n is 2^m - 1. But is seems that non-recursive segment tree solves the problem.

So, listed variations of Fenwick tree do not improve over segment tree here and all use 2*n elements.

Can we prove that a single Fenwick tree with n elements is not enough to process both range queries and updates in O(logn)?