for the past few days I've been studying Binary Indexed Tree (aka. Fenwick tree) data structure.

I understand the basic form of BIT (point update, range query), and I see the intuition behind it, but when it comes to range update - point query BIT I don't see the intuition behind it.

Let me be more specific:

  1. let tree be an array where we represent our BIT
  2. let A be an ordinary array where our array values are stored. both tree and A are initially zero

For the point update - range query, we know that tree[x], where x is some index, stores cumulative frequency for elements(values) [x - 2^r + 1, ... , x], where r is position of the last non-zero bit (looking from left to right in binary notation of number x)

Example:

  • array A: 1 3 6 7 5 5 2
  • x: ------ 1 2 3 4 5 6 7 8
  • tree(x): 1 2 1 3 2 3 1 7
  • tree(6) = 3 (6 in binary is 110, r=1, 6 - 2^1 + 1 = 5; so tree(6) stores frequencies for 5 and 6; in our example, number 5 appears 2 times and number 6 appears only once)

But, for the range update - point query i don't know the following:

a) what tree[x] represents. What is the true meaning for the value that is stored in tree[x] (for range update - point query).

b) To update range, say from a to b with value v, we will do the following operations:

  • update(a, v)
  • update(b + 1, -v)
  • and then query(x) returns value of A[x]

    Why does the query(x) returns value of A[x], what is the proof(please give some example or resource with example) for that.

In quest for the answer i found the following resources but none of them helped for the questions above:

1: https://programmingcontests.quora.com/Tutorial-Range-Updates-in-Fenwick-Tree

2: http://apps.topcoder.com/forums/;jsessionid=1749A5CAC2EA52B51F5509E8355A2CD3?module=Thread&threadID=715842&start=0&mc=8#1407869

up vote 1 down vote accepted

For BIT and its variants, I recommend this article: http://coutcode.com/blog/binaryindexedtree/

The core of BIT is point update - range query, ie. for array $A[1 \dotsc n]$, BIT supports following operations:

  1. $A[k] \leftarrow A[k] + d$ (Point update(k,d))
  2. query partial sum $S[k] = A[1] + A[2] + \dotsb + A[k]$ (Range query(k))

Other variants are just converting to 1 or more of this case.

For range update - point query, it requires support following operations for array $A[1 \dotsc n]$:

  1. $A[i] \leftarrow A[i] + d$ for all $a\le i < b$. (Range update(a,b,d))
  2. query value of $A[k]$. (Point query(k))

First, noting that after range update $A_1[i] \leftarrow A[i] + d, (a \le i \le b)$, we have $$\begin{align}A_1[a]-A_1[a-1]=&A[a]-A[a-1]+d\\A_1[b+1]-A_1[b]=&A[b+1]-A[b]-d\\A_1[i]-A_1[i-1]=&A[i]-A[i-1]\ (i\notin\{a,b+1\})\end{align}$$ Taking $$D[i] = \begin{cases}A[i],&i=1\\A[i]-A[i-1],&1<i\le n\end{cases}$$ then there are only 2 updates $$D[a]\leftarrow D[a]+d\\D[b+1]\leftarrow D[b+1]-d$$ and $$\begin{align}A[k]=&A[1]+(A[2]-A[1])+\dotsb+(A[k]-A[k-1])\\=&D[1]+D[2]+\dotsb+D[k]\end{align}$$

Thus building BIT on $D[1\dotsc n]$, we convert the range update$(a,b,d)$ on $A$ to 2 point updates $(a,d)$ and $(b+1,-d)$ on $D$, and the point query $(k)$ on $A$ is just the range query $(k)$ on $D$.

There is a simple duality between the two variants: Say you have a data structure that supports point updates and range queries A. Then we can easily turn it into a data structure B that supports range updates and point queries:

For each range update ([1..x], a) in B, do a point update (x, a) in A. For a point query x in B, do a range query [x..infinity] in A.

That's why the two versions are basically exactly the same, with the loop conditions swapped.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.