indy256's blog

By indy256, 7 years ago, In English

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:

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 2m - 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)?

 
 
 
 
  • Vote: I like it
  • +40
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Here's an algorithm which uses exactly words of storage for some constant K, by compressing one of the Fenwick trees into N/K words and performing at most 2*K-2 extra O(logN) updates per insertion: (pastebin)

Impractical, yes, but it proves that 2N is not the lowest bound possible.

»
7 years ago, # |
  Vote: I like it -40 Vote: I do not like it

Here is a good tutorial about lazy propagation. Good luck!