This post is about memory requirements for fast range queries.
First, let's consider 2 following types of queries on a sequence x..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)?